一道C语言动态规划题

#include<iostream>

#include<cstring>

using namespace std

int a[101][101],f[101][101],n,T

int maxi(int a,int b,int c)

{

if(a<b)

a=b

if(a<c)

a=c

return a

}

int main()

{

cin>>T

for(TT--)

{

cin>>n

memset(a,0,sizeof(a))

memset(f,0,sizeof(f))

for(int i=1i<=ni++)

for(int j=1j<=ncin>>a[i][j],j++)

//f[i][j]=max{f[i+1][j-1],f[i+1][j],f[i+1][j+1]}+a[i][j],1<=i,j<=n.

for(int i=ni>=1i--)

for(int j=1j<=nj++)

f[i][j]=maxi(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+a[i][j]

int maxans=-32768

for(int i=1i<=ni++)

if(f[1][i]>maxans)

maxans=f[1][i]

cout<孝斗简<maxans<<endl

}

return 0

}

这是一个我写的程序，LZ试试销岩这个可以不

你的程序唯一一处不对劲的地方，就是规划过程中的else语句。把它改成巧裤if(j!=0&&j!=m-1)试试？

在mincost函数里面，应该加上：

if(m == n)

return 0

//下面的code是我刚写的递归的石子合并，可以参考

//如果有疑问，欢迎交流

//石子合并，递归version测试通过。

#include<stdio.h>哪念乎

#define N 4

int get_sum(int *tar, int n,int head, int tail){

int cur_res = 0

int i

for(i = head i<=tail i++)

cur_res+=tar[i]

return cur_res

}

int combine_tar(int states_lib[][4], int *tar, int n, int head, int tail){

if(head == tail){

return 0

}else{

int j, cur_min = 9999999, cur_value = 0

if(states_lib[head][tail]!=0){

return states_lib[head][tail]

}

for(j = head j < tail j++){

//动态规划的状态转移方程

cur_value = combine_tar(states_lib, tar, n, head, j) + combine_tar(states_lib, tar, n, j+1, tail)

if(cur_min > cur_value){

cur_min = cur_value

}

}

states_lib[head][tail] = cur_min + get_sum(tar, n, head, tail)

return states_lib[head][tail]

}

}

int main(){

int states_lib[N][N] = {0}

int tar[N] = {4,4,5,9}

int res = combine_tar(states_lib, tar,4, 0, 3)

return 0

}

昨天就关注了这个问题，并试着写高指了石子合并，李悉但当时没有写对，刚写成功了，递归和非递归的版本，欢迎交流。

---