LeetCode 64. 最小路径和 C#
原题链接
中等
作者:
hpstory
,
2022-08-05 22:08:58
,
所有人可见
,
阅读 91
C# 二维dp 代码
public class Solution {
public int MinPathSum(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
int[][] dp = new int[n][];
for (int i = 0; i < n; i++){
dp[i] = new int[m];
Array.Fill(dp[i], int.MaxValue);
}
dp[0][0] = grid[0][0];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (i > 0) dp[i][j] = Math.Min(dp[i][j], dp[i - 1][j] + grid[i][j]);
if (j > 0) dp[i][j] = Math.Min(dp[i][j], dp[i][j - 1] + grid[i][j]);
}
}
return dp[n - 1][m - 1];
}
}
C# 一维dp 代码
public class Solution {
public int MinPathSum(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
int[] dp = new int[m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (i == 0 && j == 0) dp[0] = grid[0][0];
else if (j == 0) dp[j] = dp[j] + grid[i][j];
else if (i == 0) dp[j] = dp[j - 1] + grid[i][j];
else dp[j] = Math.Min(dp[j], dp[j - 1])+ grid[i][j];
}
}
return dp[m - 1];
}
}