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;
}