用动态规划求解问题
发布网友
发布时间：2023-08-24 02:38
共1个回答
热心网友
时间：2024-10-13 12:44
对于每个节点啊a[i][j]，它必定来自a[i-1][j]或a[i][j-1]，那么对于每个节点只要设一个同样大的数组的b[i][j]节点记录max+a[i][j]
那么核心算法可以这样表示
for(i=1;i<=k;i++)
{
for(j=1;j<=k;j++)
{
if(b[i-1][j][0]>b[i][j-1][0])
{
b[i][j][0]=b[i-1][j][0]+a[i][j];
b[i][j][1]=0; //表示选择上面路径
}
else
{
b[i][j][0]=b[i][j-1][0]+a[i][j];
b[i][j][1]=1; //表示选择右边路径
}
}
}
还有说明，把数组设大点，把b[i][0][0]和b[0][i][0]都设为0就可以节省判断边缘的时间
这样最后的b[i-1][j-1][0]一定就是最大值了
然后从b[i-1][j-1][1]一路回溯到起点就能找出路径了
