动态规划(Dynamic Programming)

基本概念

动态规划，是解决多阶段决策过程最优化的一种数学方法，把多阶段问题变换为一系列相互联系的单阶段问题，逐个加以解决。
在每一个阶段都需要作出决策，从而使整个过程达到最优。各个阶段决策的选取仅依赖当前状态（这里的当前状态指的是当前阶段的输入状态），从而确定输出状态。当各个阶段决策确定后，就组成了一个决策序列，这个决策序列就决定了问题的最终解决方案。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程。
”仅需要依赖当前状态“，指的是问题的历史状态不影响未来的发展，只能通过当前的状态去影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性(即马尔科夫性)。
和分治法的区别在于，动态规划的子问题之间是相互关联的。

基本思想

动态规划的思想是：将一个问题分解为若干个子问题，对每个子问题求最优解，前一个子问题的最优解 为下面的子问题提供了有效信息，依次解决子问题，最后一个子问题就是初始问题的最优解。即 将一个大问题化成一族互相联系、同类型的子问题。既然是同类型，我们在逐个解决子问题的时候，就可以利用相同的决策，从而更容易的解决问题。互相联系利用前面已经解决的子问题的最优化结果来依次进行计算接下来的子问题，当最后一个子问题得到最优解时，就是整个问题的最优解。
动态规划应用于子问题重叠的情况，子问题的划分是通过递归实现。为了避免子问题的重复计算，保证每个子问题只求解一次，会将解保存在数组或者Map中。

基本要素

动态规划的问题一般有两个特征：

• 最优子结构：如果一个问题的最优解包含子问题的最优解，那么该问题就具有最优子结构；（其实对应了数学中指标函数的分离性，两者只是从不同的维度描述而已）
• 重叠子问题：如果递归算法反复计算相同的子问题，那么该问题具有重叠子问题。在用递归算法自顶向下解问题时，每次产生的子问题并不是总是新问题。有些子问题被反复计算多次。动态规划算法对每一个子问题只解一次，而后将其保存在一个表格中，在之后利用这子问题的解。

另外两个重要概念（要素）：

• 边界：如果一个问题没有边界，将永远无法得到有限的结果。在划分子问题时，需要确定子问题边界，才得以求解。
• 状态转移公式：分解的每个阶段可能包含很多状态，前后阶段的状态通过决策联系在一起。如果要利用前阶段子问题的结果解决现阶段的子问题，必须要能够建立前后阶段状态的转移关系，最好能通过方程表示。专业术语叫做 状态转移方程。

  💡Tips：在衡量最优解的时候需要有一个指标函数，最优解就是让这个指标函数达到最优值，比如最大或者最小。如果我们可以将问题拆分成子问题，那么这个指标函数也必须具有分离性，也就是必须能够利用子问题的最优递推的求出整体最优。当整体最优求解出以后，就可以知道各个子问题的最优解。 状态转移方程和指标函数分离，是需要列出递推关系式，如果恰当的选取状态，让每个子问题的状态能够表示出子问题的最优解，就可以用状态转移方程递推求出指标函数的最优解。

基本步骤

动态规划的解题步骤为：
step1 最优解结构特征：找出最优解的性质，并且刻画其结构特征；
step2 递归最优值：递归地定义最优值;
step3 自底向上：以自底向上的方式，将问题分解为各个小问题，一步步地计算出最优值；
step4 最优解：根据计算最优值时得到的信息，构造一个最优解。

💡Tips：其实记录求解的方式有两种：①自顶向下的备忘录法 ②自底向上 ① 因为是树顶（根节点）到树根（末尾节点）的递归，原本父节点可以通过子节点的值获取，却要先计算父节点再求解子节点，性能相较于②大打折扣

数学方式可以看作是以下4个基本步骤：
1 确定状态 States：两个意识：子问题 (Sub problem )/ 最后一步(Last state)
2 转移方程 Transition function
3 初始条件和边界情况 Initial state / Edge cases
4 计算顺序 Order
解题考察点：

• 能够发现子问题
• 能否解出递归解
• 能否意识到递归解法的局限性
• 能否进行优化

  💡Tips：动态规划通常可以优化的点：如果数组为二维数组，可否将其转化为一维数组；如果数组为一维数组，可否将其转化为变量。空间上的优化，时间复杂度并没有改变。

经典问题

可使用分治法求解的一些经典问题：

• 斐波那契数列问题（黄金分割、兔子、爬楼梯、杨辉三角、斐波那契—卢卡斯数列）- leetcode 70 简单
• 最大子序和 - leetcode 53 简单
• 最长回文子串 - 区间模型 - leetcode 5 中等
• 最小路径和 - leetcode 64 中等
• 最长公共子串
• 编辑距离 - leetcode 72 困难
• 鸡蛋掉落
• 国王与金矿
• 背包问题
• 最长单调子序列
• 覆盖问题

  经典问题求解代码实现

  斐波那契数列(Fibonacci) - leetcode 70 简单

  有这样一个数列：1、1、2、3、5、8、13、21、34、……
  如果设an为该数列的第n项（），那么这句话可以写成如下形式：
  
  显然这是一个线性递推数列。
  在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N）
  *动态规划思想：
  1.确认原问题与子问题：
  原问题是求an的值；子问题是求1..2….n-1的值
  2.确认状态：
  第i个状态就是数列第i项的值
  3.确认边界状态的值：
  边界状态为1和2 元素的值，dp[0]=1,dp[1]=1
  4.确定状态转移方程：
  dp[i]=dp[i-1]+dp[i-2]

  const fib = function(n) {
  //校验
  if (n < 2) return n;
  const dp = []
  // 确定分界
  dp[0] = 1;
  dp[1] = 1;
  // 遍历所有内容进行运算执行
  for (let i = 2; i <= n; i++) {
    // 所有内容项目进行关联与隔离
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
  }

  由于我们仅需要第i项的前两位，所以可以用变量代替数组：

  const fib = function(n) {
  //校验
  if (n < 2) return n;
  // 确定分界
  let pre = 0, next = 0, result = 1;
  // 遍历所有内容进行运算执行
  for (let i = 1; i <= n; i++) {
    // 所有内容项目进行关联与隔离
    pre = next;
    next = result;
    result = pre + next;
  }
  return result;
  }

  最大子序和(MaxSubNumber) - leetcode 53 简单

  给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  子数组 是数组中的一个连续部分。
  动态规划思想：
  1.确认原问题与子问题：
  原问题是n个数中连续子数组最大和，子问题是以1、2、.. 、n-1为结尾的子数组的和的最大值
  2.确认状态：
  第i个状态就是以数组第i项结尾的连子数组中和的最大值
  3.确认边界状态的值：
  边界状态为第1和2 项元素结尾时的子数组和，dp[0]=nums[0], dp[1]=max(nums[1], nums[1] + dp[0])
  4.确定状态转移方程：
  dp[i]=max(dp[i-1] + nums[i], nums[i])
  5.优化：dp可以转变成使用 prev 和 result 的变量来存储前两项的值。

  const maxSubArray = function(nums) {
    if (!nums || nums.length === 0) return 0;
    let pre = 0;
    let res = nums[0];
    for (const num of nums) {
        pre = Math.max(pre + num, num);
        res = Math.max(res, pre);
    }
    return res; 
  }

  最长回文子串(LongestPalindrome) - leetcode 5 中等

  给你一个字符串 s，找到 s 中最长的回文子串。
  回文天然的 状态转移 性质：一个长度严格大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。
  动态规划思想：
  1.确认原问题与子问题：
  原问题是字符串s[0..n]的回文子串，子问题是s[1..n-1]的回文子串。所以此时数组为二维的。
  2.确认状态：
  第i,j个状态就是s[i..j]是否是回文子串。
  3.确认边界状态的值：
  边界状态为s[0]为单个字符，可以看作是回文，s[0..1]和s[0..2]则只需要判断首尾字符是否相等，即 j - i < 3 等价于 j-i+1 < 4为边界。
  4.确定状态转移方程：
  根据头尾字符是否相等，需要分类讨论：
  dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

function longestPalindrome(s: string): string {
  const len = s.length;
  if (len < 2) {
    return s; 
  }
  let maxLen = 1, start = 0;
  // dp[i][j]表示s[i:j]是否是回文串
  const dp: Array<Array<Boolean>> = new Array<Array<Boolean>>();
  for(let i = 0; i < len; i++) {
    dp[i] = [];
    // dp[i][i] = true; 
  }
  const charArray: Array<String> = s.split('');
  // 先枚举子串长度
  for (let L = 2; L <= len; L++) {
    // 枚举左边界，左边界的上限设定可以宽松些
    for (let i = 0; i < len; i++) {
      let j = L + i - 1; // L和i确定有边界
      // 处理越界
      if (j >= len) {
        break;
      }
      if (charArray[i] != charArray[j]) {
        dp[i][j] = false; 
      } else {
        if (j - i < 3) {
          dp[i][j] = true;  
        } else {
          dp[i][j] = dp[i+1][j-1]; 
        }
      }
      // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        start = i;
      }
    }
  }
  return s.substring(start, start + maxLen);
};

最长回文子串还可以通过 中心扩展法 和 manacher算法来解决，相对动态规划更高效。

最小路径和(MinPathSum) - leetcode 64 中等

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
动态规划思想：
1.确认原问题与子问题：
原问题是grid[0,0] 到 grid[m,n]的最小路径和，子问题是grid[0,0]到grid[m-1,n]或grid[m, n-1]的最小路径和。此时数组为二维的。
2.确认状态：
第i,j个状态就是grid[0,0]到grid[i,j]的最小路径和。
3.确认边界状态的值：
边界状态为grid[0,0]的最小路径和是其本身。
4.确定状态转移方程：
dp[i][j]=min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
5.优化：dp[j-1]存储dp[i-1][j]，dp[j]存储dp[i][j-1]，变量存储grid[i][j]

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    // 校验
    if(m === 0) {
        return 0;
    } else if (m === 1 && grid[0].length === 1) { // 边界
        return grid[0][0];
    }
    const n = grid[0].length;
    const dp: Array<number> = new Array(n).fill(0);
    dp[0] = grid[0][0];
    // 第一排和第一列的公式与内部的公式不同，特殊处理
    // 第一排刨去顶点的转化公式
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j-1] + grid[0][j];
    }
    for (let i = 1; i < m; i++) {
        // 第一列刨去顶点的转化公式
        dp[0] = dp[0] + grid[i][0];
        for (let j = 1; j < n; j++) {
            // 有左边点和上面点的 单元格的转化公式
            dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
        }
    }
    return dp[n-1];
};

编辑距离(MinDistance) - leetcode 72 hard

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

动态规划思想：
1.确认原问题与子问题：
原问题是word1 转化成 word2的最小操作数，子问题是word1前 m-1 个字符，变换到word2 前 n-1 个字符 的最小操作数。此时数组为二维的。
2.确认状态：
第i,j个状态就是 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数。
3.确认边界状态的值：
边界状态为考虑 word1 或 word2 一个字母都没有，即全增加/删除的情况，所以预留 dp[0][j] 和 dp[i][0]。
4.确定状态转移方程：
4.1. 增，dp[i][j] = dp[i][j - 1] + 1
4.2. 删，dp[i][j] = dp[i - 1][j] + 1
4.3. 改，dp[i][j] = dp[i - 1][j - 1] + 1
4.4. 按顺序计算，当计算 dp[i][j] 时，dp[i - 1][j] ， dp[i][j - 1] ， dp[i - 1][j - 1] 均已经确定了
4.5. 配合增删改这三种操作，需要对应的 dp 把操作次数加一，取三种的最小
4.6. 如果刚好这两个字母相同 word1[i - 1] = word2[j - 1] ，那么可以直接参考 dp[i - 1][j - 1] ，操作不用加一
5.优化：用一维数组取存储dp[i][j-1]和dp[i-1][j]的值，变量存储dp[i-1][j-1]。

function minDistance(word1: string, word2: string): number {
    const m = word1.length, n = word2.length;
    if (n === 0 || m === 0) return Math.max(n, m);
    const dp: Array<number> = new Array(n + 1).fill(0);
    for(let i=0; i<m+1; i++){
        let lu = dp[0];   // 初始化左上角变量，记录一维数组每一个位置更新前的值，即记录dp[i-1][j-1]
        dp[0] = i;  // 一维数组，dp[j]对应dp[i][j]，因此当j=0时，对应边界条件dp[i][0]=i
        for(let j=1; j<n+1; j++){
            if(i==0){
                dp[j] = j;  // 一维数组，dp[j]对应dp[i][j]，因此当i=0时，对应边界条件dp[0][j]=j
                continue;
            }
            const temp = dp[j];   // 临时变量记录更新前的值
            //更新j
            if(word1.charAt(i-1) == word2.charAt(j-1)){
                dp[j] = Math.min(dp[j-1] + 1, Math.min(dp[j] + 1, lu));
            }else{
                dp[j] = 1 + Math.min(dp[j-1], Math.min(dp[j], lu));
            }
            lu = temp; // 更新lu为j更新前的值，那么在下一次循环的时候，j变成j+，lu的值就为[i-1][j-1]
        }
    }
    return dp[n];
}

国王和金矿

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要想得到尽可能多的黄金，应该选择挖取哪几个金矿？
借助小灰大人的图：