C++三角形.为什么用动态二维数组不可以?738810274445265上图给出了一个数字三角形.从三角形的顶部到底部有很多条不同的路径.对于每条路径,把路径上面的数加起来可以

Question

C++三角形.为什么用动态二维数组不可以?
7
3 8
8 1 0
2 7 4 4
4 5 2 6
5
上图给出了一个数字三角形.从三角形的顶部到底部有很多条不同的路径.对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径.你的任务就是求出最佳路径上的数字之和.
注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数.
----------------------
#include
using namespace std;
int main()
{
int **p;
int row,col,i,j,maxsum=0;
cin>>row;
p=new int*[row];
for(i=0,col=0;i

Answer 1

局部最优不代表全局最优.
这题要用动态规划来做才行.


定义f[i][j]为(i,j)位置的最大和,则有状态转移方程：
f[0][0] = p[0][0]
f[i][0] = f[i-1][0] + p[i][0]
f[i][i] = f[i-1][i-1] + p[i][i]
f[i][j] = max{f[i-1][j-1],f[i-1][j]} + p[i][j]


最后只要取max{f[n-1][0..n-1]}即可


程序如下：
#include 
using namespace std;

int getmax(int a, int b){return a>b?a:b;}

int main()
{
\x05int **p;
\x05int **f;
\x05int n;
\x05cin >> n;
\x05p=new int*[n];
\x05f=new int*[n];
\x05for(int i=0;i\x05{
\x05\x05p[i] = new int[i+1];
\x05\x05f[i] = new int[i+1];
\x05\x05for(int j=0;j < i+1; j++)
\x05\x05{
\x05\x05\x05cin>>p[i][j];
\x05\x05\x05f[i][j] = 0;
\x05\x05}
\x05}
\x05
\x05f[0][0] = p[0][0];
\x05for(int i=1; i\x05{
\x05\x05for(int j=0; j\x05\x05{
\x05\x05\x05if(j == 0) f[i][j] = f[i-1][j] + p[i][j];
\x05\x05\x05else if(j == i) f[i][j] = f[i-1][j-1] + p[i][j];
\x05\x05\x05else f[i][j] = getmax(f[i-1][j-1], f[i-1][j]) + p[i][j];
\x05\x05}
\x05}

\x05int maxsum = f[n-1][0];
\x05for(int i=1; i\x05{
\x05\x05if(maxsum < f[n-1][i]) maxsum = f[n-1][i];
\x05}
\x05cout << maxsum << endl;

\x05for(int i=0;i\x05{
\x05\x05delete p[i];
\x05\x05delete f[i];
\x05}
\x05delete p;
\x05delete f;
\x05
\x05return 0;
}