什么是动态规划
动态规划的应用场景
动态规划解题的关键点
如何使用动态规划解决问题
动态规划的三大步骤
案例详解
示例代码
示例代码
示例代码
题目
单词拆分

什么是动态规划

动态规划是计算机中解决最优化问题的算法，效率高，速度快
动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

动态规划的应用场景

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
经典动态规划问题：

背包问题
打家劫舍
股票问题
子序列问题

动态规划解题的关键点
dp数组以及下标的含义
递推公式—转移状态方程
dp数组如何初始化
遍历顺序
打印dp数组
如何使用动态规划解决问题
如果满足上述条件，一般可以按照以下步骤进行设计：
一、确定问题的决策对象
二、对决策对象划分阶段
三、对各阶段确定状态变量
四、根据状态变量确定费用函数和目标函数
五、建立各阶段的状态变量的转移方程，写出状态转移方程
六、编程实现
动态规划的三大步骤
动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤。
第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定这个数组元素的含义。
第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。
第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。
有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么。

案例详解

案例一：简单的一维 DP

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

(1)、定义数组元素的含义

按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样，如果我们能够算出 dp[n]，所以第一步定义完成。

(2)、找出数组元素间的关系式

我们的目的是要求 dp[n]，动态规划的题，就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3…. 也就是说，dp[n] 一定会和 0dp[n-1], dp[n-2]….存在某种关系的，要找出他们的关系。
这个怎么找，是最核心最难的一个，我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？
对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式：
一种是从第 n-1 级跳上来
一种是从第 n-2 级跳上来
由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。

示例代码

function getStairs(n) {
  //如果该台阶数小于2，则输出
  if (n <= 2) return n
  //创建一个数组存储结果
  let dp = []
  dp[0] = 0
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 1]
  }
  return dp[n]
}

案例二：二维数组的 DP

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

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[i-1] [j-1] 就是我们要的答案了。
注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以右下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要找的答案。

步骤二：找出关系数组元素间的关系式

想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：
dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往右走
dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走

示例代码

var uniquePaths = function(m, n) {
if(m<1 && n<1){
return 1 
}
let dp = new Array(m).fill(0).map(()=> new Array(n).fill(0))
for(let i = 0;i<m;i++){
dp[i][0] = 1
}
for(let j = 0;j<n;j++){
dp[0][j] = 1
}
for(let i = 1;i<m;i++){
    for(let j = 1;j<n;j++){
      dp[i][j] = dp[i-1][j]+dp[i][j-1]
    }
}
return dp[m-1][n-1]
};

O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度

案例三、二维数组 DP

问题描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
举例：输入: arr = [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
和上面的差不多，不过是算最优路径和。
这是 leetcode 的第64题：https://leetcode-cn.com/problems/minimum-path-sum/

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，最小的路径和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我们要的答案了。
注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以由下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要走的答案。

步骤二：找出关系数组元素间的关系式

想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达
不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的，那么我们要从这两种方式中，选择一种，使得dp[i] [j] 的值是最小的，显然有：
dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; // arr[i][j] 表示网格中的值。

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：
dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行，机器人只能一直往左走
dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列，机器人只能一直往下走

示例代码

var minPathSum = function(grid) {
let dp = grid
let m = grid.length
let n = grid[0].length
if(m<=1 && n<=1){
    return grid[m-1][n-1]
}
for(let i = 1;i<m;i++){
    dp[i][0] = dp[i-1][0] + grid[i][0]
}
for(let j = 1;j<n;j++){
    dp[0][j] = dp[0][j-1] + grid[0][j]
}
for(let i = 1;i<m;i++){
for(let j = 1;j<n;j++){
    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]
}
}
return dp[m-1][n-1]
};

案例 4：编辑距离

问题描述:
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符删除一个字符替换一个字符

示例：输入: word1 = “horse”,word2 = “ros” 输出: 3 解释: horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

步骤一、定义数组元素的含义

由于我们的目的求将 word1 转换成 word2 所使用的最少操作数。那我们就定义 dp[i] [j]的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。
有时候，数组的含义并不容易找，所以还是那句话，我给你们一个套路，剩下的还得看你们去领悟。

步骤二：找出关系数组元素间的关系式

接下来我们就要找 dp[i] [j] 元素之间的关系了，比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，从规模小的，通过一些操作，推导出规模大的。对于这道题，我们可以对 word1 进行三种操作
插入一个字符删除一个字符替换一个字符
由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式：
一、如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。
二、如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
（1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1;
（2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1;
（3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1;
那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有
dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;
于是，我们的关系式就推出来了，

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。

题目

解析：

创建一个数组 dp[i] 用来表示以 nums[i] 结尾的最长递增子序列的长度。根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。 nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

题解：

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const dp = new Array(nums.length).fill(1);
  for (let i = 0; i < nums.length; i++) {
    // i与i前面的元素比较
    for (let j = 0; j < i; j++) {
      // 找比i小的元素，找到一个，就让当前序列的最长子序列长度加1
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  // 找出最大的子序列
  return Math.max(...dp);
};

单词拆分

var wordBreak = function (s, wordDict) {
    // dp数组,表示前index为能否被拆分
    let dp = new Array(s.length + 1).fill(false);
    // 空子前缀串默认能被拆分
    dp[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j <= i - 1; j++) {
            //存在一个字串能被拆分,并且剩余的字符串能在单词表中找到就表示当前单词能被拆分
            if (dp[j] && wordDict.indexOf(s.substring(j, i)) !== -1) dp[i] = true;
        }
    }
    return dp[s.length]
};

动态规划

什么是动态规划

动态规划的应用场景

动态规划解题的关键点

如何使用动态规划解决问题

动态规划的三大步骤

案例详解

案例一：简单的一维 DP

(1)、定义数组元素的含义

(2)、找出数组元素间的关系式

示例代码

案例二：二维数组的 DP

步骤一、定义数组元素的含义

步骤二：找出关系数组元素间的关系式

步骤三、找出初始值

示例代码

案例三、二维数组 DP

问题描述

步骤一、定义数组元素的含义

步骤二：找出关系数组元素间的关系式

步骤三、找出初始值

示例代码

案例 4：编辑距离

步骤一、定义数组元素的含义

步骤二：找出关系数组元素间的关系式

步骤三、找出初始值

题目

单词拆分