动态规划 基本介绍

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用较多，比如说让你求最长递增子序列，最短编辑距离等等。求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。

对于动态规划来说，它的穷举存在重叠子问题，如果暴力穷举的话效率极其低下，所以需要备忘录或者DP table来优化穷举过程，避免不必要地计算。而且，动态规划问题一定会具备最优子结构，才能通过子问题的最值求得原问题的最值。但问题千变万化，穷举所有可行解并不是一件容易的事，只有列出正确的状态转移方程才能正确的穷举。而重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

动态规划的一般流程

暴力的递归解法 → 带备忘录的递归解法 → 迭代的动态规划解法

重叠子问题（斐波那契数列）

1. 暴力递归

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

下面是斐波那契数列递归树

观察递归树发现许多节点被计算了多次，因此此种方法非常低效。这也是动态规划问题的第一个性质：重叠子问题。

2. 带备忘录的递归方法

将曾经解决过的子问题记录下来，省去重复计算的步骤。

int fib(int[] mono, int n) {
    if (n == 1 || n == 2) return 1;
    if (mono[n - 1] == 0)
        mono[n - 1] = fib(mono, n - 1) + fib(mono, n - 2);
    return mono[n - 1];
}

下面是带备忘录的斐波那契数列递归树

我们可以发现，这种实现方式是自顶向下的递归方式，那么为什么不跳过无用的方法栈堆积，自底而上计算斐波那契数列。

3. 动态规划（自底而上）

int fib(int n) {
    int[] mono = new int[n + 1];
    mono[1] = mono[2] = 1;
    for (int i = 3; i < mono.length; i++) {
        mono[i] = mono[i - 1] + mono[i - 2];
    }
    return mono[n];
}

下面是动态规划思路

下面是转移方程

$$\left\{ \begin{aligned} 1,n=1,2\\ f(n-1)+f(n-2),n>2 \end{aligned} \right.$$

我们发现每次进行运算，只会用到之前的两个状态，并不需要过于长的mono去储存所有的状态，可以进一步进行优化。

4. 动态规划优化

public int fib(int n) {
    if (n == 0 || n == 1)
        return n;

    int a = 1, b = 0;
    for (int i = 1; i < n; i++) {
        a = a + b;
        b = a - b;
    }
    return a;
}

最优子结构（凑零钱问题）

题目：给你 k 种面值的硬币，面值分别为c1,c2...ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1。

1. 暴力递归

该问题是动态规划问题的最优子结构，因此子问题间必须独立。为什么说它符合最优子结构呢？比如你想求amount=11时的最少硬币数（原问题），如果你知道凑出amount=10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为1的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互限制，是互相独立的。

如何列出正确的状态转移方程呢？

先确定「状态」，也就是原问题和子问题变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。

确定「DP函数」的定义，当前目标金额是n，至少需要dp[n]个硬币凑出该金额

然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表Coins中选择一个硬币，然后目标金额就会减少

# 伪代码框架
def coinChange(coins: List[int], amount: int):
	# 定义：凑出金额n,至少要dp(n)个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res
    return dp(amount)

最后明确 base case，显然目标金额为0，所需要硬币数量为0；当目标金额少于0时，无解，返回-1；

def coinChange(coins: List[int], amount: int):
    def dp(n):
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值，所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
return dp(amount)

以下是它的状态转移方程

$$\left\{ \begin{aligned} 0,n=0\\ -1,n<-1\\ min\{dp(n-coin)+1|coin\},n>0 \end{aligned} \right.$$

下面画出它的递归树

2. 带备忘录的递归

跟暴力递归写法几乎一样，只是多了一个备忘录。

public int coinChange(int[] coins, int amount) {
    int[] mono = new int[amount + 1];
    return dp(mono, coins, amount);
}

public int dp(int[] mono, int[] coins, int n) {
    if (n < 0) return -1;
    if (n == 0) return 0;
    //查备忘录避免重复计算
    if (mono[n] != 0) return mono[n];

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        int subProblem = dp(mono, coins, n - coin);
        if (subProblem == -1) continue;
        res = Math.min(res, 1 + subProblem);
    }
    //计入备忘录
    mono[n] = res != Integer.MAX_VALUE ? res : -1;
    return mono[n];
}

3. DP数组的迭代解法

自底向下使用 DP TABEL 消除重叠子问题

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    //将数组初始化为amount+1，即正无穷
    //因为求最小值，所以方便判断
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

下面画出DP TABEL数组分析

状态压缩（最长回文子序列）

动态规划技巧对于算法效率的提升非常可观，一般来说都能把指数级和阶乘级时间复杂度的算法优化成 O(N^2)，堪称算法界的二向箔，把各路魑魅魍魉统统打成二次元。但是，动态规划本身也是可以进行阶段性优化的，比如说我们常听说的「状态压缩」技巧，就能够把很多动态规划解法的空间复杂度进一步降低，由 O(N^2) 降低到 O(N)，

能够使用状态压缩技巧的动态规划都是二维dp问题，你看它的状态转移方程，如果计算状态dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩技巧，将二维的dp数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。

你看我们对dp[i][j]的更新，其实只依赖于dp[i+1][j-1], dp[i][j-1], dp[i+1][j]这三个状态：

这就叫和dp[i][j]相邻，反正你计算dp[i][j]只需要这三个相邻状态，其实根本不需要那么大一个二维的 dp table 对不对？

状态压缩的核心思路就是，将二维数组「投影」到一维数组：

思路很直观，但是也有一个明显的问题，图中dp[i][j-1]和dp[i+1][j-1]这两个状态处在同一列，而一维数组中只能容下一个，那么当我计算dp[i][j]时，他俩必然有一个会被另一个覆盖掉，怎么办？

这就是状态压缩的难点，下面就来分析解决这个问题，还是拿「最长回文子序列」问题举例，它的状态转移方程主要逻辑就是如下这段代码：

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        // 状态转移方程
        if (s[i] == s[j])
            dp[i][j] = dp[i + 1][j - 1] + 2;
        else
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
    }
}

想把二维dp数组压缩成一维，一般来说是把第一个维度，也就是i这个维度去掉，只剩下j这个维度。压缩后的一维dp数组就是之前二维dp数组的dp[i][..]那一行。

我们先将上述代码进行改造，直接无脑去掉i这个维度，把dp数组变成一维：

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        // 在这里，一维 dp 数组中的数是什么？
        if (s[i] == s[j])
            dp[j] = dp[j - 1] + 2;
        else
            dp[j] = max(dp[j], dp[j - 1]);
    }
}

上述代码的一维dp数组只能表示二维dp数组的一行dp[i][..]，那我怎么才能得到dp[i+1][j-1], dp[i][j-1], dp[i+1][j]这几个必要的的值，进行状态转移呢？

在代码中注释的位置，将要进行状态转移，更新dp[j]，那么我们要来思考两个问题：

1、在对dp[j]赋新值之前，dp[j]对应着二维dp数组中的什么位置？

2、dp[j-1]对应着二维dp数组中的什么位置？

对于问题 1，在对dp[j]赋新值之前，dp[j]的值就是外层 for 循环上一次迭代算出来的值，也就是对应二维dp数组中dp[i+1][j]的位置。

对于问题 2，dp[j-1]的值就是内层 for 循环上一次迭代算出来的值，也就是对应二维dp数组中dp[i][j-1]的位置。

那么问题已经解决了一大半了，只剩下二维dp数组中的dp[i+1][j-1]这个状态我们不能直接从一维dp数组中得到：

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        if (s[i] == s[j])
            // dp[i][j] = dp[i+1][j-1] + 2;
            dp[j] = ?? + 2;
        else
            // dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            dp[j] = max(dp[j], dp[j - 1]);
    }
}

因为 for 循环遍历i和j的顺序为从左向右，从下向上，所以可以发现，在更新一维dp数组的时候，dp[i+1][j-1]会被dp[i][j-1]覆盖掉，图中标出了这四个位置被遍历到的次序：

那么如果我们想得到dp[i+1][j-1]，就必须在它被覆盖之前用一个临时变量temp把它存起来，并把这个变量的值保留到计算dp[i][j]的时候。为了达到这个目的，结合上图，我们可以这样写代码：

for (int i = n - 2; i >= 0; i--) {
    // 存储 dp[i+1][j-1] 的变量
    int pre = 0;
    for (int j = i + 1; j < n; j++) {
        int temp = dp[j];
        if (s[i] == s[j])
            // dp[i][j] = dp[i+1][j-1] + 2;
            dp[j] = pre + 2;
        else
            dp[j] = max(dp[j], dp[j - 1]);        // 到下一轮循环，pre 就是 dp[i+1][j-1] 了
        pre = temp;
    }
}

别小看这段代码，这是一维dp最精妙的地方，会者不难，难者不会。为了清晰起见，我用具体的数值来拆解这个逻辑：

假设现在i = 5, j = 7且s[5] == s[7]，那么现在会进入下面这个逻辑对吧：

if (s[5] == s[7])
    // dp[5][7] = dp[i+1][j-1] + 2;
    dp[7] = pre + 2;

我问你这个pre变量是什么？是内层 for 循环上一次迭代的temp值。

那我再问你内层 for 循环上一次迭代的temp值是什么？是dp[j-1]也就是dp[6]，但这是外层 for 循环上一次迭代对应的dp[6]，也就是二维dp数组中的dp[i+1][6] = dp[6][6]。

也就是说，pre变量就是dp[i+1][j-1] = dp[6][6]，也就是我们想要的结果。

那么现在我们成功对状态转移方程进行了降维打击，算是最硬的的骨头啃掉了，但注意到我们还有 base case 要处理呀：

// 二维 dp 数组全部初始化为 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
    dp[i][i] = 1;

如何把 base case 也打成一维呢？很简单，记住，状态压缩就是投影，我们把 base case 投影到一维看看：

二维dp数组中的 base case 全都落入了一维dp数组，不存在冲突和覆盖，所以说我们直接这样写代码就行了：

// 一维 dp 数组全部初始化为 1
vector<int> dp(n, 1);

至此，我们把 base case 和状态转移方程都进行了降维，实际上已经写出完整代码了：

int longestPalindromeSubseq(string s) {
    int n = s.size();
    // base case：一维 dp 数组全部初始化为 1
    vector<int> dp(n, 1);

    for (int i = n - 2; i >= 0; i--) {
        int pre = 0;
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];
            // 状态转移方程
            if (s[i] == s[j])
                dp[j] = pre + 2;
            else
                dp[j] = max(dp[j], dp[j - 1]);
            pre = temp;
        }
    }
    return dp[n - 1];
}