Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(figure 1)
input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle,all integers,are between 0 and 99.Output
Your program is to write to standard output. The highest sum is written as an integer.Sample input
573 88 1 0 2 7 4 44 5 2 6 5
Sample Output30方法:动态规划:Step 1:确定状态:
题目求解(1,1)到最底层路径的最大权值,路径起点固定,终点和中间点不确定,因此定义dg[x][y]表示从(1,1)出发到(x,y)路径的最大权值和。
最终答案就是寻找最底层的最大值,ans=max{dp[n][1],dp[n][2],dp[n][3]...dp[n][n]}.
Step 2:确定状态转移方程和边界条件:
不去考虑(1,1)到(x,y)中间是怎么走的,只需要考虑(x,y)上一步是怎么来的,上一步可能是(x-1,y),也可能是(x-1,y-1),因此dg[x][y]的最大值就是上一步的最大权值和:max{dp[x-1][y],dp[x-1][y-1]),再加上自己的权值a[x][y]。
所以状态转移方程就是:dp[x][y]=max{dp[x-1][y],dp[x-1][y-1]}+a[i][j]。
与递归一样,我们也需要终止条件,防止无限递归下去。我们发现dp[x][y]的值取决于dp[x-1][y],dp[x-1][y-1],随着递归的深入,最后一定会递归到dp[1][1],dp[1][1]不能再使用状态转移方程了,所以给dp[1][1]附一个初值,即a[1][1]。
my codes:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[550][550],dp[550][550]; 4 int n; 5 int main() 6 { 7 cin>>n; 8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=n;j++)10 cin>>a[i][j];11 dp[1][1]=a[1][1];12 for(int i=2;i<=n;i++)13 {14 for(int j=1;j<=i;j++)15 {16 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];17 }18 }19 int ans=0;20 for(int i=1;i<=n;i++) ans=max(ans,dp[n][i]);21 cout<<ans<<endl;22 return 0;23 }
更进一步的探索:https://blog.csdn.net/weixin_40851250/article/details/83622717
@H_419_0@ 总结以上是内存溢出为你收集整理的The Triangle全部内容,希望文章能够帮你解决The Triangle所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)