动态规划

【动态规划】，Dynamic Programming, DP
过程：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以这种多阶段最优化决策解决问题的过程 称为【动态规划】

思路

【动态规划】是一种特殊的分治，与【分治算法】的思路类似：

• 将待求解的问题分解为若干个子问题（阶段）
• 按顺序求解子阶段，前一子问题的解为后一子问题的求解提供了有用的信息；
• 在求解任一子问题时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，丢弃其他局部解；
• 依次解决各个子问题，最后一个子问题就是初始问题的解。

由于【动态规划】解决的问题有重叠子问题的特点，为了让每个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中，即 以空间换时间

与【分治算法】最大的区别是：适合于用【动态规划】求解的问题，经分解后得到的子问题往往【不是互相独立的】，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

特性

采用【动态规划】求解的问题通常具备三个特性：

• 最优子结构：（自上而下）
• 无后效性：某阶段的状态一旦确定，就不受之后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关，反之亦然。
• 重叠子问题：（自下而上）子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
  这个性质并不是【动态规划】适用的必要条件，但如果没有这条性质，【动态规划算法】同其他算法相比就不具备优势。

基本步骤

【动态规划】所处理的问题是一个 多阶段决策的问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优活动路线）

初始状态 -> |决策-1| -> |决策-2| -> ... -> |决策-n| -> 结束状态

• 【划分阶段】：按照问题的时间和空间特征，把问题划分为若干个阶段。注意：划分后的阶段一定要是有序的或可排序的，否则问题就无法求解。
• 【确定状态和状态变量】：将问题求解到各个阶段时、所处于的各种客观情况用不同的状态表示出来，当然状态的选择要满足【无后效性】
• 【确定决策并给出状态转移方程】：决策和状态转移有着天然联系，【状态转移】就是根据上一阶段的状态和决策导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上，常常反过来做：根据相邻两个阶段的状态之间的联系来确定决策方法和状态转移方程
• 【寻找边界条件】：给出的状态转移方程是一个递推式的，需要一个递推的终止条件。

确定动态规划的三要素：

• 问题的阶段
• 每个阶段的状态
• 从前一个阶段转移到下一个阶段之间的递推关系

递推关系 必须是从【次小问题】开始到【较大问题】之间的转化，从这个角度来讲，【动态规划】往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也就是【动态规划算法】的核心之处。

确定了【动态规划】的三要素之后，整个求解过程就可以用一个【最优决策表】来描述，最优决策表是一个二维表（或一维表）。其中，行表示决策的阶段，列表示问题的状态。表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径、最长公共子序列、最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或列优先的顺序，一次填写表格，最后根据整个表格的数据、通过简单的取舍或运算求得问题的最优解。

f(n, m) = max{ f(n-1, m), f(n-1, m - w[n]) + P(n, m) }

动态规划的解题套路

【动态规划】无非就是利用 历史记录 来避免重复计算，而这些历史记录一般使用 一维数组 或 二维数组 来保存。

• 步骤一：定义数组元素的含义。可以理解为拆分成子问题
  数组是用来保存历史记录的，那么就必须规定数组元素的含义。假设使用一维数组dp，规定 dp[i]代表什么意思
• 步骤二：数组元素之间的关系式。可以理解为子问题重叠
  类似数学归纳法，当计算 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[3] = dp[2] + dp[1]，而 dp[2] 和 dp[1] 是不可分解的，所以必须能够获取dp[2] 和 dp[1]的值，即 初始值。

一维数组 之 青蛙跳台阶

正常青蛙

问题：一只青蛙一次跳 1 个台阶，也可以跳 2 个台阶，请问 跳 N 个台阶有多少种跳法？

• 定义 数组元素的含义
  问题是求青蛙跳上 n 级台阶总共由多少种跳法，那么就可以用一个一维数组来保存跳法，定义 dp[i] 的含义为：跳上一个 i 级台阶总共有 dp[i] 种跳法。计算出 dp[n] 也就是需要的答案。

• 找出 数组元素间的关系式
  【动态规划】也是把一个规模较大的问题分解成规模较小的子问题，解出小问题推导出大问题的解。dp[n]的规模为n，比它规模小的是n-1、n-2、n-3...，也就是说dp[n] 一定和dp[n-1]、dp[n-2]、...存在某种关系。
  分析：
  青蛙一次可以跳 1 或 2 个台阶，那么跳上n 个台阶的跳法f(n)就有两种情况：

  • 从第 (n-1) 个台阶跳 1 阶，这类跳法有f(n-1)种
  • 从第 (n-2) 个台阶跳 2 阶，这类跳法有f(n-2)种

  可以得出，跳到 n 个台阶的跳法 等于 跳到 n-1 个台阶 与 跳到 n-2 个台阶之和，即f(n) = f(n-1) + f(n-2)，类似斐波那契数列，反映到数组元素的关系式为 dp[n] = dp[n-1] + dp[n-2]

• 找出 初始值
  当 n = 1，时，dp[1] = dp[0] + dp[-1]，而数组下标不允许为负数，所以必须直接给出 dp[1] 的值，dp[1] = 1，即 初始值。
  同理，n = 0表示没有跳台阶，即dp[0] = 0，而dp[2] = dp[1] + dp[0] = 1 + 0 = 1，而实际上dp[2] = 2，所以 初始值 的设定为 n <= 2 时，dp[n] = n

# 迭代版本
function jump(n){
    if(n <= 2){
        return n;
    }
    // 假装使用数组：这样会造成空间复杂度为 O(n)
    // 其实可以直接使用 【变量】 代替，这样空间复杂度优化成 O(1)
    let dp = [0, 1, 2]
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

# 递归版本
function jump(n, start = 1, end = 1){
    if(n <= 2){
        return n
    }
    return jump(n - 1) + jump(n - 2)
}

# 尾递归优化
function jump(n, start = 1, end = 0){
    if(n === 0){
        return end;
    } else if(start === 0) {
        start = 1
    }
    return jump(n - 1, end, start + end);
}

变异青蛙

问题：一只青蛙一次跳 1 个台阶，也可以跳 2 个台阶、3个台阶、4个台阶、...、n个台阶，请问 跳 N 个台阶有多少种跳法？
分析：同理，跳上 n 级台阶有 n 种跳法，f(n) = f(n-1) + f(n-2) + ... + f(1)
又由 f(n-1) = f(n-2) + f(n-3) + ... + f(1) 可知，f(n) = 2f(n-1) = 2^(n-1)*f(1) = 2^(n-1)*1
得：f(n) = 2^(n-1)，n > 2。当n <= 2 时，f(n) = n

二维数组

其实，【动态规划】解题时大多数使用的都是 二维数组

机器人走方格（路径规划）

一个机器人位于 M x N 网格的左上角，每次只能向下或向右移动一步，到达网格右下脚一共有多少条不同的路径？

机器人走网格

• 步骤一：定义数组元素的含义
  既然是一个M x N的网格，那么元素dp[i][j] 就表示其中一个格子，dp[0][0] 表示左上角，dp[m-1][n-1] 表示右下角。
  数组元素 dp[i][j] 的含义：当机器人从左上角走到(i, j)位置时，一共有 dp[i][j] 种路径。

• 步骤二：分析数组元素之间的关系式
  机器人可以向下走，也可以向右走，所以到达 dp[i][j] 位置有两种方式

  • 从 dp[i-1][j] 位置走一步达到
  • 从 dp[i][j-1] 位置走一步达到

  计算所有可能的方式 就是把走的路径相加，所以关系式为 dp[i][j] = dp[i-1][j] + dp[i][j-1]

• 步骤三：确定初始值
  对于dp[i][j]，如果 i = 0 或 j = 0，关系式就不再成立了，因为数组角标不能为负数。
  所以，初始值就是算出所有的dp[0][0] + dp[0][1] + ... + d[0][n-1] 和所有的dp[0][0] + dp[1][0] + ... + dp[m-1][0]，它们分别表示：一直右走（一条路径）、一直向下走（一条路径）
  得初始值：

  • dp[0][0...n-1] = 1 一直向右走
  • dp[0...m-1][0] = 1 一直向下走

public int solution(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

空间复杂度的优化：由状态转移方程式dp[i][j] = dp[i-1][j] + dp[i][j-1] 可知，当填充第 i 行的值时，只需要知道第i-1行的值，从第1行到第i-2行都是不需要的！
https://zhuanlan.zhihu.com/p/91582909

进阶版

保持问题的题意，在网格中增加障碍物，机器人无法越过障碍物
分析：虽然增加了障碍物，但关系式还是适用的，不过需要些许改变

• 对于正下方和正右方的路径，一旦遇到障碍物，就表示无法通过，则后面的路径全是0
• 障碍物所处的点本身不可达，也导致后面的所有点都不可达，即存储值为0

// 给定一个二维数组，如果某个元素值为 1，表示有障碍物
public int uniquePathsWithObstacles(int[][] matrix) {
    if(matrix == null) return 0;
    if(matrix[0][0] == 1) {  // 起点有障碍物，不可达
        return 0;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    if(matrix[row-1][col-1] == 1) {  // 重点有障碍物，不可达
        return 0;
    }
    // 构建路径二维数组
    int[][] dp = new int[row][col];
    // 初始化起点，开始有 1 条路径
    dp[0][0] = 1;
    // 第一列: 初始化值都是 1
    for(int i = 1; i < row; i++) {
        if(matrix[i][0] != 1) {  // 没有障碍物
            dp[i][0] = dp[i-1][0];
        }
    }
    // 第一行: 初始化值都是 1
    for(int j = 1; j < col; j++) {
        if(matrix[0][j] != 1) {  // 没有障碍物
            dp[0][j] = dp[0][j-1];
        }
    }
    // 计算其他所有路径
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
            if(matrix[i][j] == 1) continue;  // 障碍物
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[row-1][col-1];
}

最小路径之和

给定一个M x N的网格，每次只能向下或向右移动一格，请找出一条从左上角到左下角的路径，使得路径上的数字总和最小。

arr = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
// 最小路径 1 -> 3 -> 1 -> 1 -> 1，总和为 7

• 步骤一：定义数组元素的含义
  dp[i][j] 的含义：从左上角(0, 0)走到坐标(i, j)的位置时，最小路径之和为d[i][j]。
  那么，d[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] 表示目的网格的值
  

• 步骤三：初始值
  数组角标的最小值为 0，所以(i、j) >= 0。初始值也就是计算出所有的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-1][0]
  

public int uniquePath(int[][] arr) {
    int row = arr.length;
    if(row == 0) return 0;
    int col = arr[0].length;
    if(col == 0) return 0;
    
    int[][] dp = new int[row][col];
    // 初始化
    dp[0][0] = arr[0][0];
    // 第一列的初始化
    for(int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 第一行的初始化
    for(int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + arr[0][j];
    }
    // 推导 dp[row-1][col-1]
    for(int i = 1; i < row; i++) {
        for int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[row-1][col-1];
}
// O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度

编辑距离

给定两个单词 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-1][j]、dp[i][j-1]、dp[i-1][j-1] 存在某种关系。
分析：
由题可知：对 word1 的操作有三种：插入、删除、替换 一个字符
要想让操作的次数最小，就要寻找最佳操作：

• 如果word1[i] == word2[j]，则不需要做任何操作，那么把【字符串word1 的前 i 个字符】转化为【字符串word2 的前 j 个字符】的操作步数 与 【前i-1】转换成【前j-1】的操作步数是相等的，即 dp[i][j] = dp[i-1][j-1]
• 如果word1[i] != word2[j]，那么就必须对字符串word1 进行调整，且有三种操作可选：
  • 删除
    想象一下，什么情况下仅仅对word1 删除一个元素就可以完成【前i 个字符转换成word2 的前j 个字符】呢？
    删除一个字符，意味着【word1的前i-1 个字符已经转换成了word2 的前j 个字符】，所以对word1 的转换就是 删除第i个字符 这一个操作步数。
    可得表达式：dp[i][j] = dp[i-1][j] + 1
  • 插入
    对word1 插入一个字符才能完成转换，也就是说已经将word1 的前i个字符转换成了word2 的前j-1 个字符，那么现在只需要再对word1 追加一个与【word2 的第j 个字符】相等的字符就完成了。
    因此可得：dp[i][j] = dp[i][j-1] + 1
  • 替换
    将word1 的第 i 个字符替换成 word2 的第 j 个字符，也就是说【word1的前i-1个字符】已经转换成了【word2的前j-1个字符】，再跟进 替换 这一步即可。
    可得关系式：dp[i][j] = dp[i-1][j-1] + 1

至此，通过三种操作得到了三种dp[i][j]的关系式，并且利用了之前保存的状态，所以只需要 取其中最少的步数 即可的得到原问题的解。
总关系式：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

步骤三：初始值

数组角标不能为负数，而当 i=0 或 j=0 时，关系式中的 i - 1 和 j - 1 就得到了负数的角标。所以，初始值就是计算出所有dp[0][0...j]和所有的dp[0...i][0]。
由二维数组dp 的含义可知，角标表示两个字符串的长度，当i=0 或 j=0时，也就是有一方字符串的长度为0，那么只需要 删除 或 插入 操作即可。

• 对于dp[0][j]来说，将长度为 0 的字符串word1 转换成长度为 j 的字符串word2，只需要不断地对word1 执行 插入操作，总操作步数为j

  dp[0][j] = j
  

• 同理，对于dp[i][0]，则不断地对word1 执行 删除操作，总操作步数为i

  dp[i][0] = i
  

实现代码

function convert(s1, s2) {
    let m = s1.length
    let n = s2.length
    // 构建二维数组：长度比字符串大 1，是因为关系式的角标不能为 0
    let dp = new Array(m+1).fill(new Array(n+1))
    // dp[0...m][0] 初始化
    for(let i = 0; i < m+1; i++) {
        dp[i][0] = i
    }
    // dp[0][0...n] 初始化
    for(let j = 0; j < n+1; j++) {
        dp[0][j] = j
    }
    // 数组元素之间的关系
    for(let i = 1; i < m+1; i++) {
        for(let j = 1; j < n+1; j++) {
            if(s1[i-1] === s2[j-1]) {
                // 两个字符相等，则无需操作，即操作步数与前一步相等
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 取最小操作步数 + 1 就是当前操作步数
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}