Posted on 2023-03-27 13:32
Uriel 阅读(26)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
给出一个二维数组，问从左上角的格子不断向右向下走到右下角的格子，一路经过的所有各自的数字之和最小是多少，简单dp
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
C++版
1 //64
2 //Runtime: 168 ms Beats 5.30%)
3
4 class Solution {
5 public:
6 int dp[1010][1010];
7 int minPathSum(vector<vector<int> > &grid) {
8 if(grid.empty()) return 0;
9 for(int i = 0; i < grid.size(); ++i) {
10 for(int j = 0; j < grid[0].size(); ++j) {
11 if(!i && !j) dp[i][j] = grid[i][j];
12 else if(!i) dp[i][j] = dp[i][j - 1] + grid[i][j];
13 else if(!j) dp[i][j] = dp[i - 1][j] + grid[i][j];
14 else
15 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
16 }
17 }
18 return dp[grid.size() - 1][grid[0].size() - 1];
19 }
20 };
Python版：
1 #64
2 #Runtime: 114 ms (Beats 11.96%)
3 #Memory: 14.8 MB (Beats (61.34%)
4
5 class Solution(object):
6 def minPathSum(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 dp = [[0]*len(grid[0]) for _ in range(len(grid))]
12 print(dp)
13 for i in range(len(grid)):
14 for j in range(len(grid[0])):
15 if not i and not j:
16 dp[i][j] = grid[i][j]
17 elif not i:
18 dp[i][j] = dp[i][j - 1] + grid[i][j]
19 elif not j:
20 dp[i][j] = dp[i - 1][j] + grid[i][j]
21 else:
22 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
23 return dp[-1][-1]