动态规划-P1216 [IOI 1994] 数字三角形 Number Triangles

P1216 [IOI 1994] 数字三角形 Number Triangles

题目来源-洛谷题库

思路

• 如果用贪心只是找当前的到达该点的路径最大值，可能结果无法做到最优
• 最值问题试着看能否将大问题分解成若干个小问题 走到a[i] [j ]这个点的最值来源于上一步a[i-1 ] [j]和a[i-1] [j-1]的最值
• 因此 设置状态：dp[i] [j] 储存到j j 这个点的路径的最值
• 状态转移方程: dp[i] [j] = max(dp[i-1] [j],dp[i-1] [j-1])+dp[i] [j]; 但是要注意边界：最左端和最右端只有一条路径的情况
• 注意初始化：dp[1] [1] = a[1] [1],注意边界
  

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1005][1005], dp[1005][1005];//分别储存权值和走到该点的路径最大值 
int main() {cin >> n;for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)cin >> a[i][j];dp[1][1] = a[1][1]; // 初始条件for(int x = 2; x <= n; x++)for(int y = 1; y <=x; y++) {if(y-1==0){ //只存在来源于右上方dp[x][y] = dp[x-1][y]+a[x][y];//只存在来源于左上方（数组的正上方） }else  if(x-1<y){dp[x][y] = dp[x-1][y-1]+a[x][y];}else{dp[x][y] = max(dp[x-1][y],dp[x-1][y-1])+a[x][y];  //两个方向 } // 注意计算总和时，不要忘记有加上这格子的权重}int ans = -1e5;for(int i = 1; i <= n; i++)ans = max(ans,dp[n][i]);// 最后一行找最大值作为答案cout << ans << endl;return 0;
}