该篇将陆续收集动态规划一系列相关问题
image.pngimage.png

1.Leetcode.931下降路径最小和

难度中等
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：
动态规划例题合集 - 图3
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：如图所示，为和最小的两条下降路径
示例 2：
动态规划例题合集 - 图4
输入：matrix = [[-19,57],[-40,-5]] 输出：-59 解释：如图所示，为和最小的下降路径

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100

  • -100 <= matrix[i][j] <= 100

    1.1思路分析

    仔细阅读题意，该题目要求我们求最小的路径和，这是一个很明显的求最值问题，

  • 状态（一直在改变的量）：最短路径和

  • 选择（引起状态改变的动作）：由image.png

可知是当前位置的上方，左上和右上引起了当前位置的改变

  • base case: i=0时（即第一行），所有列的元素是已知的为matrix[0][j]

我们要求最短的路径和，只需要对比上、左上和右上的路径长度，取最短的路径加上当前格子的路径长度。所以，我们设dp（matrix数组，行，列）函数，返回值为当前位置的最短路径。

1.2代码

1.2.1暴力递归

  1. class Solution {
  2.     public int minFallingPathSum(int[][] matrix) {
  3.         int n=matrix.length;
  4.         int min=Integer.MAX_VALUE;
  5.         for(int j=0;j<n;j++){
  6.             min=Math.min(min,dp(matrix,n-1,j));
  7.         }
  8.         return min;
  9.     }
  11.     public static int dp(int[][] matrix,int i,int j){
  12.         if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length)
  13.             return 99999;
  14.         if(i==0)
  15.             return matrix[i][j];
  16.         return matrix[i][j]+min(
  17.             dp(matrix,i-1,j),
  18.             dp(matrix,i-1,j-1),
  19.             dp(matrix,i-1,j+1)
  20.         );
  21.     }
  22.     public static int min(int a,int b,int c){
  23.         return Math.min(a,Math.min(b,c));
  24.     }
  25. }

超出时间限制

1.2.2带备忘录的递归

  1. class Solution {
  2.     int[][] memo;
  3.     public int minFallingPathSum(int[][] matrix) {
  4.         int n=matrix.length;
  5.         memo=new int[matrix.length][matrix[0].length];
  6.         for(int i=0;i<matrix.length;i++){
  7.             Arrays.fill(memo[i],66666);
  8.         }
  9.         int res=Integer.MAX_VALUE;
  10.         for(int j=0;j<matrix.length;j++){
  11.             res=Math.min(res,dp(matrix,n-1,j));
  12.         }
  13.         return res;
  14.     }
  15.     public int dp(int[][] matrix,int i,int j){
  16.         if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length)
  17.             return 99999;
  18.         if(i==0)
  19.             return matrix[0][j];
  20.         if(memo[i][j]!=66666)
  21.             return memo[i][j];
  22.         memo[i][j]=matrix[i][j]+min(
  23.             dp(matrix,i-1,j),
  24.             dp(matrix,i-1,j-1),
  25.             dp(matrix,i-1,j+1)
  26.             );
  27.         return memo[i][j];
  28.     }
  30.     int min(int a,int b,int c){
  31.         return Math.min(a,Math.min(b,c));
  32.     }
  33. }

image.png

1.2.3自底向上的dp数组