题目链接:https://www.luogu.com.cn/problem/P1216;
有两种思路:递推和记忆化搜索。
先说递推:
我们采取从底到上的遍历思路,这样相比于从上往下更可节省时间,不至于造成TLE,所以dp【i】【j】就表示第i层第j个数开始往下走的数字和。
具体代码如下:
#include<bits/stdc++.h> using namespace std; int r; int dp[1010][1010];//第i层第j个数字开始向下走的数字和 int a[1010][1010];//第i层第j个数字 int main() { ios::sync_with_stdio(false); cin>>r; for(int i=0;i<r;i++)//杨辉三角的输入形式 for(int j=0;j<=i;j++) cin>>a[i][j]; for(int j=0;j<r;j++) dp[r-1][j]=a[r-1][j];//先计算底部 for(int i=r-2;i>=0;i--)//从倒数第二层向上到第一层 { for(int j=0;j<=i;j++) { dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];//从左边上来或者是从右边上来,取其大 } } cout<<dp[0][0]<<endl; return 0; }
当然,我们可以引入记忆化搜索:
因为在测试样例中我们可以看到第三行第二列的1是被重复递归的,因为从它左上边的3递归计算下来之后,从8下来也被重复递归计算,这样就会造成时间上的浪费,应用了记忆化搜索则会减少这一流程的时间。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int r; 4 int dp[1010][1010];//第i层第j个数字开始向下走的数字和 5 int a[1010][1010];//第i层第j个数字 6 int dfs(int i,int j) 7 { 8 if(i==r-1)//边界条件,到了最底层 9 return a[i][j]; 10 if(dp[i][j]>0)//记忆化标记,初始值是0,如果大于0就不用在重复递归计算了 11 return dp[i][j]; 12 return dp[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]; 13 } 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 cin>>r; 18 for(int i=0;i<r;i++)//杨辉三角的输入形式 19 for(int j=0;j<=i;j++) 20 cin>>a[i][j]; 21 dfs(0,0);//执行递归一直到最底部然后返回到dp[0][0] 22 cout<<dp[0][0]<<endl; 23 return 0; 24 }