dp题，基本一次过
1 class Solution { 2 public: 3 int minPathSum(vector<vector<int> > &grid) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 int m = grid.size(); 7 if (!m) return 0; 8 int n = grid[0].size(); 9 if (!n) return 0; 10 vector<vector<int>> f(m, vector<int>(n)); 11 f[0][0] = grid[0][0]; 12 for (int i = 1; i < m; i++) f[i][0] = f[i-1][0]+grid[i][0]; 13 for (int i = 1; i < n; i++) f[0][i] = f[0][i-1]+grid[0][i]; 14 for (int i = 1; i < m; i++) { 15 for (int j = 1; j < n; j++) { 16 f[i][j] = min(f[i][j-1], f[i-1][j])+grid[i][j]; 17 } 18 } 19 return f[m-1][n-1]; 20 } 21 };
C#
1 public class Solution { 2 public int MinPathSum(int[,] grid) { 3 int m = grid.GetLength(0); 4 int n = grid.GetLength(1); 5 if (m == 0 || n == 0) return 0; 6 int[,] f = new int[m, n]; 7 f[0, 0] = grid[0, 0]; 8 for (int i = 1; i < m; i++) f[i, 0] = f[i-1, 0] + grid[i, 0]; 9 for (int i = 1; i < n; i++) f[0, i] = f[0, i-1] + grid[0, i]; 10 for (int i = 1; i < m; i++) { 11 for (int j = 1; j < n; j++) { 12 f[i, j] = Math.Min(f[i, j-1], f[i-1, j]) + grid[i, j]; 13 } 14 } 15 return f[m-1, n-1]; 16 } 17 }