64. Minimum Path Sum (Medium)

题目描述
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
思路
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int x = grid.length;
  4.         int y = grid[0].length;
  5.         int[][] dp = new int[x][y];
  6.         //初始化
  7.         dp[0][0] = grid[0][0];
  8.         for(int i=1; i<y; i++){
  9.             dp[0][i] = dp[0][i-1] + grid[0][i];
  10.         }
  11.         for(int i=1; i<x; i++){
  12.             for(int j=0; j<y; j++){
  13.                 if(j==0){
  14.                     dp[i][j] = dp[i-1][j]  + grid[i][j];
  15.                 }else{
  16.                     dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
  17.                 }
  18.             }
  19.         }
  20.         return dp[x-1][y-1];
  21.     }
  22. }

内存优化

思路
只需要记录上一行的dp即可。

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int x = grid.length;
  4.         int y = grid[0].length;
  5.         int[] dp = new int[y];
  6.         //初始化
  7.         dp[0] = grid[0][0];
  8.         for(int i=1; i<y; i++){
  9.             dp[i] = dp[i-1] + grid[0][i];
  10.         }
  11.         for(int i=1; i<x; i++){
  12.             for(int j=0; j<y; j++){
  13.                 if(j==0){
  14.                     dp[j] = dp[j]+grid[i][j]; 
  15.                 }else{
  16.                     dp[j] = Math.min(dp[j-1],dp[j]) + grid[i][j];
  17.                 }
  18.             }
  19.         }
  20.         return dp[y-1];
  21.     }
  22. }

结果
image.png

62. Unique Paths (Medium)

题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例
输入：m = 3, n = 7
输出：28

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp =new int[m][n];
  4.         //初始化
  5.         for(int i=0; i<n; i++){
  6.             dp[0][i] = 1;
  7.         }
  8.         for(int i=0; i<m; i++){
  9.             dp[i][0] = 1;
  10.         }
  11.         for(int i=1; i<m; i++){
  12.             for(int j=1; j<n; j++){
  13.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  14.             }
  15.         }
  16.         return dp[m-1][n-1];
  17.     }
  18. }

内存优化

同上

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[] dp = new int[n];
  4.         //初始化
  5.         for(int i=0; i<n; i++){
  6.             dp[i] = 1;
  7.         }
  8.         for(int i=1; i<m; i++){
  9.             for(int j=1; j<n; j++){
  10.                 dp[j] = dp[j-1] + dp[j];
  11.             }
  12.         }
  13.         return dp[n-1];
  14.     }
  15. }

image.png