1.动态规划介绍

动态规划，英文：Dynamic Programming，简称DP，动态规划的思路一般是把一个复杂问题转化成一个个子问题, 然后分阶段逐步递推, 从一个简单的初始状态一步一步递推, 最终得到一个复杂问题的最优解, 动态规划也有分治的**.

1.1解决的问题

动态规划问题的形式大部分都是求最值, 或者最优解, 比如有求最长递增子序列, 最长公共子序列等等.

• 子序列问题
• 背包类型问题
• 贪心类型问题

1.2使用限制

• 重叠子问题
  一个问题可以拆分成很多个子问题, 并且在求解过程中存在同样的子问题重复计算
• 最优子结构
  问题的最优解包含子问题的最优解, 也就是说可以根据一个子问题的最优解, 推导出这个问题的最优解, 对应到动态规划问题之上, 也就是后面阶段的状态可以通过前面状态推导出来, 并且子问题之间互相独立.
• 无后效性
  主要有两个含义. 第一, 在推导后面问题或者阶段状态的时候，我们只关心前面的状态值，不关心这个状态值是怎么一步步推导出来的. 第二, 某阶段状态值一旦确定，就不受之后阶段的决策影响.

1.3解题步骤

一般动态规划解决的都是最值问题, 而求解最值的核心方法是穷举, 但是因为重叠子问题的特性,直接穷举效率很低, 所以通过备忘录的形式优化穷举过程, 一般叫: dp table. 又因为最优子结构的特性, 那么可以通过子问题的最值得到问题的最值. 大部分的动态规划问题都会经历下面几个步骤:

• 划分状态, 也就是确定划分子问题及含义
• 确定状态表示
  确定dp数组（dp table）值以及下标的含义
• 确定状态转移
  父问题如何通过子问题推导出来的,也就是上一阶段状态如何推导出本阶段的状态
• 确定边界
  也就是明确问题的初始状态及最终状态, 一般需要确定初始状态, 也就是初始化 dp table 的值, 然后求出最终状态

总结套路就是

# 初始化 dp table
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

1.4实现方式

• 递归
  这种方式是自上向下的，通过dp(n)到dp(n-1)
• 递推
  这种方式是自下向上的，通过dp(0) 推导出 dp(1), 再由 dp(2) 推导出 dp(3)

2.过程举例

2.1斐波那契数列-重叠子问题

(1) 暴力递归

int f(int N) {
    if (N == 1 || N == 2) return 1;
    return f(N - 1) + f(N - 2);
}

计算原问题 f(20)，就要先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。在这个过程中,会发现有很多子问题被重复计算,这就是动态规划的第一个性质: 重叠子问题 .

(2) 带备忘录的递归

int f(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return helper(memo, N);
}
int helper(int[] memo, int n) {
    // 确定边界
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

通过递归树,可以看到备忘录避免了重复计算,这种方式已经和动态规划解法差不多了, 然后这种递归的方式就是我们刚刚说的自上向下的解法: ** 都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案 ** , 自下向上就是反过来, 直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（边界,初始状态）开始往上推，直到推到想要的答案 f(20)。这就是「递推」的思路，大部分动态规划都是使用递推，而是由循环迭代完成计算.

(4) dp 数组递推解决

上述中的备忘录就叫做 DP table . 通过这个表 自下向上 进行递推, 得到结果

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
   // 初始化状态
    dp[0] = 0; dp[1] = 1;
    // 进行状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

然后列出状态转移方程

2.2 零钱兑换-状态转移方程

解决步骤

1. 判断最优子结构
   比如想求 amount = 11 时的最少硬币数，如果知道凑出 amount = 10 的最少硬币数（子问题），那么只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。
2. 确定状态
   原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额可以分解成子问题，所以唯一的「状态」就是目标金额 amount
3. 确定状态表示
   首先讨论自顶向下的解法，会有一个递归的 dp 函数，函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的值。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
4. 初始化状态
   当目标金额 amount 为 0 时算法返回 0

所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

递归解法

// 定义：要凑出金额 amount/n，至少要 dp(coins, amount) 个硬币
int dp(int[] coins, int amount) {
    // 边界条件
    if (amount == 0) return 0;
    int res = Integer.MAX_VALUE;
    if (amount < 0) return Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == Integer.MAX_VALUE) continue;
        // 在子问题中选择最优解, 选择硬币最少的解，然后加上当前需要的一枚硬币
        res = Math.min(res, subProblem + 1);
    }
    return res;
}

然后上面选择最优解的过程就是状态转移的过程

递推解法

自底向上使用 dp table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：
dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1，初始值也为 amount + 1, 表示无解
    Arrays.fill(dp, amount + 1);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

3.例题

最长递增子序列

首先定义 dp table: dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
根据这个定义, 就可以确定初始状态: dp[i] 全部初始化为 1, 因为以 nums[i] 结尾的递增子序列至少包括它自己.
演示:

根据以上,那么 dp table 中最大的值就是这道题的结果

如果已经知道了 dp[0...4] 的值, 那么如何根据已知结果推导出 dp[5] 的值呢?
按照对 dp 数组的定义, 现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一, 可能形成很多种新的子序列，但是只选择最长的那一个，把最长子序列的长度作为 dp[5] 的值即可

int lengthOfLIS(int[] nums) {
    // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
    int[] dp = new int[nums.length];
    // 初始化dp 数组全都初始化为 1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) 
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

第一个标题

• a
• b

第二个