题目链接

最小路径和

题目描述

image.png

实现代码

动态规划思想：记dp[i][j]为从起点(0, 0)到(i,j)的最小路径和，首先初始化条件：

  1. dp[0][0] = grid[0][0];
  2. dp[0][j] = grid[0][j] + dp[0][j-1];
  3. dp[i][0] = grid[i][0] + dp[i-1][0];

动态转移方程为：

dp[i][j] = Math.max(dp[i-1][j]. dp[i][j-1]) + grid[i][j]

实现代码：

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  4.         int m = grid.length;
  5.         int n = grid[0].length;
  7.         int[][] dp = new int[m][n];
  8.         dp[0][0] = grid[0][0];
  9.         for (int i = 1; i < m; i++) {
  10.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  11.         }
  12.         for (int j = 1; j < n; j++) {
  13.             dp[0][j] = dp[0][j - 1] + grid[0][j];
  14.         }
  16.         for (int i = 1; i < m; i++) {
  17.             for (int j = 1; j < n; j++) {
  18.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  19.             }
  20.         }
  22.         return dp[m - 1][n - 1];
  23.     }
  24. }

在二维数组动态规划的基础上进行降维优化，实现代码：

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int n = grid.length, m = grid[0].length;
  4.         int[] f = grid[0];
  5.         for(int i = 1; i < m; i++) f[i] += f[i - 1];
  6.         for(int i = 1; i < n; i++){
  7.             for(int j = 0 ; j < m; j++){
  8.                 if(j > 0) f[j] = Math.min(f[j], f[j - 1]) + grid[i][j];
  9.                 else f[j] += grid[i][j];
  10.             } 
  11.         }
  12.         return f[m - 1];
  13.     }
  14. }