数字金字塔问题描述考虑在下面被显示的数字金字塔第n行有n列。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每前进一步可以走到它的正下方或者右下方往下一行、往右一列的位置。73 88 1 02 7 4 44 5 2 6 5在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30输入说明第一个行包含 R(1 R1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。输出说明输出仅一行包含那个可能得到的最大的和。输入范例6 7 3 8 8 1 0 2 7 4 100 4 5 2 6 5 3 2 5 8 7 6输出范例129解法1dfs//解法1:dfs #includebits/stdc.h using namespace std; int arr[1010][1010]; //千万别用use数组用了就代表每一行中只能选不重复的列就会导致一直是斜着的不会访问到下一行的本列即正下方 int t; int Max-1; //col是记录从上一层的哪一列下来的 void dfs(int u,int res,int col){ if(ut){ if(resMax)Maxres; return ; } for(int icol;icol2iu;i){ resresarr[u][i]; dfs(u1,res,i); resres-arr[u][i]; } } int main(){ cint; for(int i0;it;i) for(int j0;ji;j) cinarr[i][j]; dfs(0,0,0); coutMaxendl; }解法2dp//解法2动态规划 #includebits/stdc.h using namespace std; //f[i][j]从头到i行j列的所有数字路径的集合属性最大值 int f[1010][1010]; int t; int Max-1; int main(){ cint; for(int i1;it;i) for(int j1;ji;j) cinf[i][j]; for(int i1;it;i) for(int j1;ji;j) f[i][j]max(f[i-1][j-1],f[i-1][j])f[i][j]; //遍历最下面一行获取最大值即位正解 for(int i1;it;i) if(f[t][i]Max)Maxf[t][i]; coutMaxendl; return 0; }