想了很久 沒(méi)有想到很好的方法 后來(lái)看見(jiàn)評(píng)論里有一個(gè)方法很好 我研究了一下 發(fā)現(xiàn)挺巧妙地 所以發(fā)上來(lái) 以備以后看
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<vector<int>> dp(triangle.size(), vector<int>(triangle.size(), 0)); //初始化一個(gè)寬為riangle.size()（這個(gè)是上式的第二個(gè)） 高為riangle.size()的矩陣（上式的第一個(gè)）
for(int i = 0; i <= triangle.size() - 1; i++){
dp[triangle.size() - 1][i] = triangle[triangle.size() - 1][i];
}//將原三角矩陣中的最后一行賦值給 新的dp矩陣的最后一行
for(int i = triangle.size() - 2; i >= 0; i--){
for(int j = 0; j <= i; j++){
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];//這里是核心代碼 建議畫(huà)出來(lái)理解下
}
}
return dp[0][0];
}
};
