[leetcode] 120 Triangle

[leetcode] 120 Triangle

感覺acm做過之後，這種題太基本了....

沒啥好說的，最簡單的動態規劃，找出狀態轉移方程就可以了。采用由下到上的思想（這樣最後只需要取出dp[0][0]就是答案），本層每個結點的結果根據下面一行的路基累計和而計算，要麼取左邊的，要麼取右邊的，兩者取最小的即可。
狀態轉移方程：triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])

class Solution {
public:
  int minimumTotal(vector > &triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j){
      	
        triangle[i][j] +=min(triangle[i+1][j+1],triangle[i+1][j]);
      }
    
    return triangle[0][0];
  }
};

稍微進階一點的： hdu 1176 免費餡餅

思路：可將所有的時間段和餡餅看成是一個矩陣，時間就是行數，掉餡餅的就是列數，則就是數字三角形問題，從最底層找一條路徑，使得路徑上的和最大。狀態轉移方程為:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j-1])+pie[i][j]。pie[i][j]為時間i時在j位置掉的餡餅數目。

具體代碼這裡就不貼出了，大家盡量去實現一下。