动态规划概念理解

动态规划，英文：Dynamic Programming，简称DP，是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，和贪心的不同就在于，它的每一个子问题的答案都是通过上一个子问题的答案递推过来的，贪心才不会管之前的过程。它和递归的不同在于，它能够把已有子问题的答案保存下来（dp数组），避免重复计算。比如斐波那契数列的递推写法和递归写法，就体现了dp和递归的区别。

动态规划的分析主要有以下4点：

• 状态定义

  • 大问题化为小问题。

• 状态转移分析

  • 分情况讨论，做到不重不漏，把不同的选择情况都列出来
  • 抓住变(已知)与不变(未知)的部分，即思考要更新的状态应该从哪个已知状态转移过来，两个状态有什么关系。

• 初始化

  • 对最小子问题进行初始化，一般就是对一些边界情况赋初值

• 返回值

  • 一般是返回最后一个状态

01背包

125 · 背包问题（二） - LintCode

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

1. A[i], V[i], n, m 均为整数
2. 你不能将物品进行切分
3. 你所挑选的要装入背包的物品的总大小不能超过 m
4. 每个物品只能取一次
5. $m<=1000$

$len(A),len(V)<=100$

样例

样例 1：

输入：

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

输出：

9

解释：

装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

样例 2：

输入：

m = 10
A = [2, 3, 8]
V = [2, 5, 8]

输出：

10

解释：

装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

挑战

O(nm) 空间复杂度可以通过, 你能把空间复杂度优化为O(m)吗？

问题：从所以物品中选，背包所能装的最大价值

子问题：从部分物品中选，背包所能装的最大价值

状态：f(i, j) 从前 i 个物品中选，所占体积小于等于 j 的方案中的最大价值

状态转移：

对于一件物品，有两种情况，分析每一种情况时，我们先不考虑得到的f(i, j)是不是最大价值：

• 不选，那么一定有 f(i, j) = f(i - 1, j)
• 选，因为是选完之后得到 f(i, j) ，那么选之前一定是 f(i - 1, j - a[i])，再加上 v[i] 就是 f(i, j) 即 f(i, j) = f(i - 1, j - a[i]) + v[i]，注意这种情况下一定有j >= a[i]，否则不选

最后在这两种情况中取最大值：

状态转移方程：
$$\mathrm{f}(\mathrm{i},\mathrm{j})=\{\begin{array}{ll}\mathrm{f}(\mathrm{i}-1,\mathrm{j}),& \mathrm{j}<\mathrm{a}[\mathrm{i}]\\ \max (\mathrm{f}(\mathrm{i}-1,\mathrm{j}),\mathrm{f}(\mathrm{i}-1,\mathrm{j}-\mathrm{a}[\mathrm{i}])+\mathrm{v}[\mathrm{i}]),& \mathrm{j}>=\mathrm{a}[\mathrm{i}]\end{array}$$
初始化：f(0, j) = 0，f(i, 0) = 0

以样例1为例，画个表：

因为更新状态都是用上一行较左边的值，所以遍历方式从左往右从上至下

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

得到答案f(4, 10) = 9。

代码实现就比较简单了，但是要注意题目给的数组是往往是从0开始计，我们分析问题是从1开始计，所以在使用题目给定的数组时，要在分析好的i, j上减1，或者你也可以在题目给的数组前面头插一个无效值。

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &a, vector<int> &v) {
        int n = a.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= a[i - 1]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + v[i - 1]);
            }
        }
        return dp[n][m];
    }
};

空间优化：

注意观察，每次状态更新，都是用的数组上一行较左边的值，那么二维数组其实可以改用一维数组

把和行有关的定义及使用删去。

第二层遍历要从后往前，这样左边的值就是原来二维数组上一行的值

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &a, vector<int> &v) {
        int n = a.size();
        vector<int> dp(m + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = m; j >= 1; --j) // 注意遍历顺序
            {
                if (j >= a[i - 1]) dp[j] = max(dp[j], dp[j - a[i - 1]] + v[i - 1]);
            }
        }
        return dp[m];
    }
};

分割回文串 II

132. 分割回文串 II - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

问题：s 分割成几个回文串的最小分割次数

状态：f(i)：s 的前 i 个字符的最小分割次数

状态转移：

• 如果前 i 个就是回文串，那么最小分割次数就是 0，f(i) = 0
• 如果前 i 个不是回文串，但是已知 f(j)，0 < j < i，那么我们只需要看 [j+1, i] 的字符串是不是回文串
  • 如果是，则可以在第j个字符后面切一刀，完成回文串分割f(i) = f(j) + 1
  • 如果不是，则不考虑，至于在 [j+1, i] 这部分究竟要切几刀，会有 f(k),j+1 <= k < i 去计算。
  • 最后要在这些 f(j) 中取最小的一个，f(i) = min(f(j)) + 1, 0 < j < i

状态转移方程：
$$\mathrm{f}(\mathrm{i})=\{\begin{array}{ll}0,& \mathrm{前}\mathrm{i}\mathrm{个是回文串}\\ \min (\mathrm{f}(\mathrm{j}))+1,0<\mathrm{j}<\mathrm{i},& \mathrm{前}\mathrm{i}\mathrm{个不是回文串}\end{array}$$
初始化：f(0) = 0，并让 f(i) = i - 1,i >= 1，表示前 i 个字符的最大分割次数，方便和 f(j) 比大小求最小值

class Solution {
public:
    bool isPal(string& s, int left, int right)
    {
        while (left < right)
        {
            if (s[left] != s[right]) return false;
            ++left;
            --right;
        }
        return true;
    }

    int minCut(string s) {
        int n = s.size();
        vector<int> f(n + 1, 0);
        for (int i = 2; i <= n; ++i)
        {
            f[i] = i - 1;
        }
        for (int i = 2; i <= n; ++i)
        {
            if (isPal(s, 0, i - 1)) f[i] = 0;
            else
            {
                for (int j = 1; j < i; ++j)
                {
                    if (isPal(s, j, i - 1)) f[i] = min(f[i], f[j] + 1);
                }
            }
        }
        return f[n];
    }
};

时间复杂度：$O(n^3)$，这里出现了三层循环遍历，isPal 判断回文串本身也是一次遍历。

空间复杂度：$O(n)$，创建了一个n+1个元素的一维数组

优化：

以空间换时间，对于判断回文串，也可以使用动态规划：

问题：判断从下标i到下标j的字符串是否是回文串

状态：f(i, j)：[i, j]区间内的字符串是否为回文串

状态转移：

f(i, j) = (s[i] == s[j]) && f(i + 1, j - 1)

其中i > j 不用考虑

初始化：

• i = j时，则 f(i, j) = true

• i + 1 = j， 即范围内只有两个相邻的字符，f(i, j) = s[i] == s[j]

初始化和状态转移可以写在一起。

注意这里的状态转移是用的下一行 i + 1，那么更新顺序应该是从下往上。

最后要判断是否回文的时候直接访问这个数组就可以了。

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) // 注意循环遍历的顺序
        {
            for (int j = i; j < n; ++j)
            {
                if (i == j) isPal[i][j] = true;
                else if (j == i + 1) isPal[i][j] = s[i] == s[j];
                else
                {
                    isPal[i][j] = (s[i] == s[j]) && isPal[i + 1][j - 1];
                }
            }
        }

        vector<int> f(n + 1, 0);
        for (int i = 2; i <= n; ++i)
        {
            f[i] = i - 1;
        }
        for (int i = 2; i <= n; ++i)
        {
            if (isPal[0][i - 1]) f[i] = 0;
            else
            {
                for (int j = 1; j < i; ++j)
                {
                    if (isPal[j][i - 1]) f[i] = min(f[i], f[j] + 1);
                }
            }
        }
        return f[n];
    }
};

时间复杂度：$O(n^2)$ ，只有两个二层循环

空间复杂度：$O(n^2)$，构建了一个判断是否回文的二维数组

编辑距离

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

问题：word1 到word2 的编辑距离

子问题：word1的局部到word2的局部的编辑距离

状态：f(i, j)：word1的前i个字符到word2的前j个字符的编辑距离

状态转移：

f(i, j) 无非就是从三个状态转移过来：f(i, j - 1)、f(i - 1, j)、f(i - 1, j - 1)

• 先看 f(i, j) 和 f(i, j - 1) 有什么关系，先将 word1 前 i 个转换成 word2 前 j - 1 个，并得到编辑距离 f(i, j - 1)，在此基础上，加上一个插入操作就可以让 word1 前 i 个转换成 word2 前 j 个，即 f(i, j) = f(i, j - 1) + 1
• 再看 f(i, j) 和 f(i - 1, j) 的关系，先将 word1 前 i - 1 个转换成 word2 前 j 个，并得到编辑距离 f(i - 1, j)，在此基础上，只要删除 word1 的第 i 个，就可以转换成 word2 的前 j 个，f(i, j) = f(i - 1, j) + 1
• 最后看 f(i, j) 和 f(i - 1, j - 1)，先将 word1 前 i - 1 转换成 word2 前 j - 1 个，并得到编辑距离 f(i - 1, j - 1)，在此基础上，看 word1 的第 i 个和 word2 的第 j 个是否相同，若相同，则不动，即 f(i, j) = f(i - 1, j - 1)，若不同，则需要替换一次，即 f(i, j) = f(i - 1, j - 1) + 1。

最后的状态转移方程，就是从这三者之中选最小的那个。
$$\mathrm{f}(\mathrm{i},\mathrm{j})=\{\begin{array}{ll}\min (\mathrm{f}(\mathrm{i},\mathrm{j}-1)+1,\mathrm{f}(\mathrm{i}-\mathrm{i},\mathrm{j})+1,\mathrm{f}(\mathrm{i}-1,\mathrm{j}-1)),& word1\mathrm{第}\mathrm{i}\mathrm{个字符等于}word2\mathrm{第}\mathrm{j}\mathrm{个字符}\\ \min (\mathrm{f}(\mathrm{i},\mathrm{j}-1)+1,\mathrm{f}(\mathrm{i}-\mathrm{i},\mathrm{j})+1,\mathrm{f}(\mathrm{i}-1,\mathrm{j}-1)+1),& word1\mathrm{第}\mathrm{i}\mathrm{个字符不等于}word2\mathrm{第}\mathrm{j}\mathrm{个字符}\end{array}$$
初始化：f(0, j) = j，f(i, 0) = i

class Solution {
public:
    int minDistance(string word1, string word2) {
        int row = word1.size();
        int col = word2.size();
        vector<vector<int>> f(row + 1, vector<int>(col + 1, 0));
        for (int i = 1; i <= col; ++i)
        {
            f[0][i] = i;
        }
        for (int i = 1; i <= row; ++i)
        {
            f[i][0] = i;
        }
        for (int i = 1; i <= row; ++i)
        {
            for (int j = 1; j <= col; ++j)
            {
                f[i][j] = f[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) f[i][j] += 1;
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
            }
        }
        return f[row][col];
    }
};

时间复杂度：$O(mn)$

空间复杂度：$O(mn)$

不同的子序列

115. 不同的子序列 - 力扣（LeetCode）

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

• 0 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

问题：s 中与 t 相同的子序列的个数

子问题：与上一题类似，s 的局部子串中与 t 的局部相同的子序列的个数

状态：f(i, j)：s 的前 i 个字符中与 t 的前 j 个相同的子序列的个数

状态转移：

• 如果选择 s 的第 i 个字符作为子序列的一部分，那么它一定是子序列的最后一个，也就是 t 的第 j 个字符，那么一定有 s[i] = t[j] ，f(i, j) = f(i - 1, j - 1)

• 如果不选 s 的第 i 个字符，那么有两种情况

  • s[i] != t[j]，f(i, j) = f(i - 1, j)
  • s[i] = t[j]，但是我们不选，f(i, j) = f(i - 1, j)

最后整合一下，把 s[i] = t[j] 算成一种情况，在这一条件下，有 f(i, j) = f(i - 1, j) + f(i - 1, j - 1)，这里可以直接相加，因为一个是构成 t 的前 j 个字符的子序列的个数，另一个是构成 t 的前 j - 1 的字符的子序列个数，二者不存在重复

状态转移方程：
$$\mathrm{f}(\mathrm{i},\mathrm{j})=\{\begin{array}{ll}\mathrm{f}(\mathrm{i}-1,\mathrm{j})+\mathrm{f}(\mathrm{i}-1,\mathrm{j}-1),& \mathrm{s}[\mathrm{i}]=\mathrm{t}[\mathrm{j}]\\ \mathrm{f}(\mathrm{i}-1,\mathrm{j}),& \mathrm{s}[\mathrm{i}]\ne \mathrm{t}[\mathrm{j}]\end{array}$$
初始化：

• f(i, 0) = 1, 0 <= i <= s.size：任意一个字符串中都有一个空子序列
• f(0, j) = 0, 0 < j <= t.size：从空字符串中找不到非空子序列

class Solution {
public:
    int numDistinct(string s, string t) {
        int row = s.size();
        int col = t.size();
        if (row < col) return 0;
        vector<vector<unsigned long long>> f(row + 1, vector<unsigned long long>(col + 1, 0));
        for (int i = 0; i <= row; ++i)
        {
            f[i][0] = 1;
        }
        for (int i = 1; i <= row; ++i)
        {
            for (int j = 1; j <= col; ++j)
            {
                if (s[i - 1] == t[j - 1])
                    f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                else
                    f[i][j] = f[i - 1][j];
            }
        }
        return f[row][col];
    }
};

使用一维数组进行空间优化，类似背包问题，第二层循环需要从后往前更新，保证前面的值是上一层的：

class Solution {
public:
    int numDistinct(string s, string t) {
        int row = s.size();
        int col = t.size();
        if (row < col) return 0;
        vector<unsigned long long> f(col + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= row; ++i)
        {
            for (int j = col; j >= 1; --j)
            {
                if (s[i - 1] == t[j - 1])
                    f[j] = f[j] + f[j - 1];
            }
        }
        return f[col];
    }
};