基础DP算法思想的整理

简介

DP, 全称 dynamic programming, 动态规划，意思是对于规模较大的任务是由一个个规模较小的任务完成的，在解决问题期间会遇到一个个状态，任意一个状态的解决往往是依赖上一个或多个状态的解决来推进，所以需要一个状态转移方程，通过状态转移方程能够解决任意一个状态的问题，并由此解决下一个状态，以及最终状态的值。

我们从几个基础的DP问题，可以感受到这种状态转移的具体表现，并总结遇到DP问题时我们最先考虑的思路应该是什么。

70. 爬楼梯算法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ **注意：**给定 n 是一个正整数。

解析

爬楼梯算法是非常经典的DP算法，问题的结论是到达楼顶时能有多少种方法。

我们可以这样想，因为确定了只能爬一个或两个台阶，所以对于楼梯的任意一级台阶n，我们只有两种方式能到达，一种是从第(n-1)级台阶跳一个台阶，第二种是从第(n-2)级台阶跳2级台阶。那对于楼顶同样如此。

所以可以推测: 到达第n级台阶的方法数 = 到达第n-1级台阶的方法数 + 到达第n - 2级台阶的方法数。

这就是本问题的转移方程了，那么这时候我们可以开始溯源。当只有一级台阶的时候有几种方法呢，明显只有一种，那两级台阶时有几种呢，明显有两种，0到1到2和0到2。如此这般就进入了我们的状态转移大法，由两个很容易确定的值dp[1]和dp[2]，可以推广到dp[3],dp[4]以及dp[n];


dp[3] = dp[1] + dp[2];

dp[4] = dp[3] + dp[2];

... 
dp[n] = dp[n - 1] + dp[n - 2];

代码


/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const dp = [];
  dp[0] = 0;
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
};
// @lc code=end

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：


输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：


输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length

n == obstacleGrid[i].length

1 <= m, n <= 100

obstacleGrid[i][j] 为 0 或 1

解析

这题和爬楼梯看上去很类似，但是似乎非常的复杂，容易让人摸不着头脑。

但是仔细思考可以看到他同样给我们一个DP的条件

机器人每次只能向下或者向右移动一步

由这个条件我们能想到，对于图上的任意一个点，只有两种方式能到，从上面来，从左边来，而当前位置能到达的路径数就等于到达上边那个点的路径数加上从左边来的路径数，于是得到状态转移方程:

到达grid[n][m]的路径数 = 到达grid[n-1][m]的路径数 + 到达grid[n-1][m-1]的路径数

同时结合这个题目给了两个限制:

对于最左边一列和最上边一行的点，其路径数只能是由上边或者左边的点决定。

对于有障碍物的点，达到他的路径数为0

然后溯源，对于dp[0][0]位置的值，取决于当前点是否有障碍物，即起始点是否有障碍物，如果起始点都有障碍物，那好像之后也没必要算了。


dp[0][0] = grid[0][0] === 1 ? 0 : 1; (或者使用1^grid[0][0])

dp[0][1] = dp[0][0]; // 由于是上边一行，只能为

dp[1][0] = dp[1][0]; // 最左边一列

// 先看是不是障碍物
// 不是的话就计算从上面和从左边来的 
dp[1][1] = grid[1][1] ? 0 : dp[1][0] + dp[0][1];

代码


/*
 * @lc app=leetcode.cn id=63 lang=javascript
 *
 * [63] 不同路径 II
 */

// @lc code=start
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {

  const dp = Array.from({ length: obstacleGrid.length }, () => (Array.from({ length: obstacleGrid[0].length }, () => 0)));

  dp[0][0] = 1 ^ obstacleGrid[0][0];

  if (!dp[0][0]) {
    return 0;
  }

  for (let i = 0; i < obstacleGrid.length; i++) {
    for (let j = 0; j < obstacleGrid[0].length; j++) {
      if (i === 0 && j === 0) {
        continue;
      }
      if (obstacleGrid[i][j] === 1){
        dp[i][j] = 0;
      }else if (i === 0) {
        dp[0][j] = dp[0][j - 1];
      } else if (j === 0) {
        dp[i][0] = dp[i - 1][0];
      } else {
        dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i][j - 1] + dp[i - 1][j];
      }
    }

  }

  return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
};
// @lc code=end

53. 最大子序列和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：


输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：


输入：nums = [1]
输出：1

示例 3：


输入：nums = [0]
输出：0

示例 4：


输入：nums = [-1]
输出：-1

示例 5：


输入：nums = [-100000]
输出：-100000

解析

这个相对来说和前面的两道题有些差别，它的要求是求连续的子数组的和，且这个和是最大的，那对于数组中的任意一个值，假设它是子数组中的一个，那他可以选择加上前面的连续数组，或者不加上前面的连续数组，如果前面连续数组加上当前值的结果比不加前面的连续数组的当前值的结果要大，那么肯定要加上前面的连续数组，否则不加。这个点一旦想同，那么就非常简单了；


dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])

溯源，对于dp[0]来说就是nums[0]的值


dp[1] = Math.max(dp[0] + nums[1], nums[1])
...
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])

而我们要找的是其中最大的那个值，也就是Math.max(...dp);

当然我们也可以在循环中用一个max变量存上当前最大的值，减少一次循环。

这里的key在于想通，当前位置的连续数组的最大值取决于是否和前面的连续数组组成一个新的数组，判断条件则是合并后的和比只取当前值为新连续数组哪个更大。

代码


/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子序和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  const dp = [];

  dp[0] = nums[0];

  let max = dp[0];

  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

    max = Math.max(dp[i], max);
  }

  return max;
};
// @lc code=end

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：


输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：


输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：


输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500

104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解析

这题又和上一题不尽相同，他是一个子序列，并不要求连续，但是要求递增。

首先假设对于某一个元素之前的元素都已经找到了自己的最长递增子序列，那我这个元素是否要加入某一个最长递增子序列，需要考虑什么呢:

我是不是比这个最长递增子序列的最后一个数大，比最后一个数大才能加入

这个最长递增子序列是不是我能加入的最长递增子序列，我要找一个能加入的且最长的子序列加入，才能保证下一个比我大的元素加入我所在的子序列时，他也会组成最长的子序列

想通这两个逻辑就能明白我们的状态转移方程是啥了。


for(let j = 0; j < i; j++){
	dp[i] = 0;
	if(nums[i] > nums[j]){
		dp[i] = Math.max(dp[j] + 1, dp[i]);
	}
}

这虽然不是一个严格的状态转移方程，但是说明了，我们要找到某一个元素为最后一个元素的最长子序列的方法。

同样我们用一个max变量去保存中途找到的最长的递增子序列

这题说明dp的题并不是都是只看前面一个，或者固定个数的元素，而是根据题型确定，这是我们需要着重注意的。

代码


/*
 * @lc app=leetcode.cn id=300 lang=javascript
 *
 * [300] 最长递增子序列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {

  const dp = [];

  dp[0] = 1;

  let max = 1;

  for (let i = 1; i < nums.length; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
        max = Math.max(dp[i], max);
      }
    }  
  }

  return max;
};
// @lc code=end

120. 三角形最短路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：


输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
23 4
 65 7
41 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：


输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

104 <= triangle[i][j] <= 104

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

解析

这题和不同路径II那道题类似，限制了上一步的来源，考虑边界情况，计算最短路径和。不是什么大问题.

代码


/*
 * @lc app=leetcode.cn id=120 lang=javascript
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const dp = Array.from({ length: triangle.length }, () => []);

  dp[0][0] = triangle[0][0];

  for (let i = 1; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      if (j === 0) {
        dp[i][0] = triangle[i][0] + dp[i - 1][0];
      } else if (j === triangle[i].length - 1) {
        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
      }
    }
  }

  // console.log(dp)
  return Math.min(...dp[triangle.length - 1]);
};
// @lc code=end