{% tabs %} {% tab title="CPP" %}
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if (triangle.size() == 0) return 0;
int n = triangle.size();
vector<int> dp(n,0);//初始化很重要
// dp = triangle[n - 1]
for (int i = 0; i < triangle[n-1].size();i ++) {
dp[i] = triangle[n-1][i];
cout << triangle[n-1][i];
}
for (int i = n -2 ; i > -1; i --){
for (int j = 0; j <= i; j ++) {
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
}
}
return dp[0];
}
};{% endtab %}
{% tab title="Python" %}
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
## 既然是path 那就dfs
return self.dfs(0, 0, triangle)
def dfs(self,level, idx, nums):
if level == len(nums) - 1: # 到葉子了
return nums[level][idx]
## 對比 root.left
left = self.dfs(level+1,idx,nums)
right = self.dfs(level+1,idx + 1,nums)
root = nums[level][idx] + min(left,right)
## 後序
return root
{% endtab %}
{% tab title="DFS" %}
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
## 既然是path 那就dfs
visited = [[-1] *(i+1) for i in range(len(triangle))]
return self.dfs(0, 0, triangle,visited)
def dfs(self,level, idx, nums,visited):
if level == len(nums) - 1: # 到葉子了
return nums[level][idx]
if visited[level][idx]!=-1:
return visited[level][idx]
## 對比 root.left
left = self.dfs(level+1,idx,nums,visited)
right = self.dfs(level+1,idx + 1,nums,visited)
root = nums[level][idx] + min(left,right)
visited[level][idx] = root
## 後序
return root
{% endtab %}
{% tab title="DP" %}
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
## 下到上
dp = [0] * len(triangle[-1])
dp[:] = triangle[-1]
## 行
for i in range(len(triangle)-2,-1,-1):
## 列,
for j in range(0, i+1):
dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
return dp[0]
{% endtab %} {% endtabs %}