【C++】动态规划

参考博客：动态规划详解

1. 什么是动态规划

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

1.1 重叠子问题与最优子结构

1.1.1 重叠子问题

重叠子问题是指在问题的求解过程中，存在多次使用相同的子问题的情况，即在求解问题的不同阶段，需要求解的子问题可能是相同的。重叠子问题是动态规划算法设计的基础之一，利用子问题的重叠性可以减少重复计算，提高算法效率。

1.1.2 最优子结构

最优子结构是指问题的最优解可以通过子问题的最优解来构造得到。也就是说，问题的最优解包含子问题的最优解。通俗地说，就是大问题的最优解可以由小问题的最优解推出。这是动态规划的关键性质之一。

1.1.3 举例

举个例子，假设有一个包含n个元素的序列，需要找出其中的最长递增子序列（LIS，Longest Increasing Subsequence）。这个问题就具有最优子结构性质。如果一个序列的LIS已知，那么如果在其末尾添加一个元素，就有两种情况：

如果该元素大于当前LIS的末尾元素，那么新序列的LIS为当前LIS加上这个元素，长度为原序列的LIS长度加1；
如果该元素小于等于当前LIS的末尾元素，那么当前LIS不会受到影响，新序列的LIS仍然是原序列的LIS。

因此，该问题的最优解可以通过已知的子问题的最优解构造得到。

1.2 动态规划的核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

我们来看下，网上比较流行的一个例子：

A ： "1+1+1+1+1+1+1+1 =？"
A ： "上面等式的值是多少"
B ： 计算 "8"
A : 在上面等式的左边写上 "1+" 呢？
A : "此时等式的值为多少"
B : 很快得出答案 "9"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

1.3 从青蛙跳台阶进入动态规划

leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法

1.3.1 解题思路

基本思想：动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从f(1)往f(10）方向，往上推求解，所以称为自底向上的解法。

什么意思，我们从第一个台阶往上推，假设跳到第n级台阶的跳数我们定义为f(n):

当只有1级台阶时，只有一种跳法，即f（1）= 1；

当只有2级台阶时，有两种跳法。第一种是直接跳两级。第二种是先跳一级，然后再跳一级。即f(2) = 2;

当有3级台阶时，也有两种跳法。第一种是从第1级台阶直接跳两级。第二种是从第2级台阶跳一级。即f(3) = f(1) + f(2);

要想跳到第4级台阶，要么是先跳到第3级，然后再跳1级台阶上去;要么是先跳到第2级，然后一次迈2级台阶上去。即f(4) = f(2) + f(3);

此时，我门就能得到公式：

f(1) = 1;
f(2) = 2;
f(3) = f(1) + f(2);
f(4) = f(2) + f(3);
…
f(10) = f(8) + f(9);
即f(n) = f(n – 2) + f(n – 1)。

此时我们来看看动态规划的典型特征在此题中的展现：

最优子结构：f(n-1)和f(n-2) 称为 f(n) 的最优子结构。
重叠子问题：比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。
状态转移方程：f(n)= f(n-1)+f(n-2)就称为状态转移方程。
边界：f(1) = 1, f(2) = 2 就是边界。

1.3.2 代码

代码思路如图：

代码实现：

class Solution {
public:
    int numWays(int n) {
        int dp[101] = {0};
        int mod = 1000000007;

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= mod;
        }

        return dp[n] % mod;
    }
};

这个方法空间复杂度是O(n)，但是呢，仔细观察上图，可以发现，f（n）只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求了，因此空间复杂度是O(1)就可以啦。

代码实现：

class Solution {
public:
    int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = (a + b)% 1000000007;
            a = b;
            b = temp;
        }
        return temp;
    }
};

2. 动态规划解题套路

2.1 核心思想

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。并且动态规划一般都是自底向上的，因此到这里，基于青蛙跳阶问题，总结了一下做动态规划的思路：

穷举分析
确定边界
找出规律，确定最优子结构
写出状态转移方程

2.1.1按例分析

穷举分析

当台阶数是1的时候，有一种跳法，f（1） =1
当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;
当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3
当台阶是4级时，想跳到第3级台阶，要么是先跳到第3级，然后再跳1级台阶上去，要么是先跳到第 2级，然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5
当台阶是5级时…

确定边界

通过穷举分析，我们发现，当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。f(1) =1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3) = f(2) + f(1) =3，因此f(1) =1，f(2) = 2就是青蛙跳阶的边界。

找规律，确定最优子结构

n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构。什么是最优子结构？有这么一个解释：

一道动态规划问题，其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

通过前面3步，穷举分析，确定边界，最优子结构，我们就可以得出状态转移方程啦：

3. 例题

3.1 递增子序列

3.1.1. 穷举分析：

当nums只有10的时候，最长子序列[10]，长度1。
当nums加入9时，最长子序列[10]或[9]，长度1。
当nums加入2时，最长子序列[10]或[9]或[2]，长度1。
当nums加入5时，最长子序列[2, 5]，长度2。
当nums加入3时，最长子序列[2, 5]或[2, 3]，长度2。
当nums加入7时，最长子序列[2, 5, 7]或[2, 3, 7]，长度3。
…
当nums再加入一个元素18时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4。

3.1.2 确定边界

对于nums数组的每一个元素而言，当我们还没有开始遍历寻找时，它们的初始最长子序列就是它们本身长度为1。

3.1.3 找规律，确定最优子结构

通过上面分析，我们可以发现一个规律：

nums[i]结尾的自增子序列，只要找到结尾nums[j]比nums[i]小的子序列，加上nums[i] 就可以。显然，可能形成多种新的子序列，我们选最长那个，就是的最长递增子序列。

得到最优子结构：

最长递增子序列(nums[i]) = max(最长递增子序列(nums[j])) + nums[i]; 0<= j < i, nums[j] < nums[i];

3.1.4 写出状态转移方程

我们设立dp数组储存以nums数组的元素结尾的最长子序列的长度，将其初始化为1，由最优子结构得到状态转移方程：

dp[i] = max(dp[j]) + 1; 0<= j < i, nums[j] < nums[i];

3.1.5 代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

3.2 最长字符串链

这个题和上题是很相像的，但是注意，这个题并没有要求词链的单词顺序必须时按照原单词数组的顺序。

3.2.1 穷举分析

这里注意，因为这个题并没有要求词链的单词顺序必须时按照原单词数组的顺序，所以我们分析也不能按照原单词数组的顺序穷举分析。按照词链的特性，我们应该从原单词数组中长度最短的单词开始，向长度最长的单词穷举分析。

示例1:

当words只有”a”时，最长词链[“a”]，长度1。
当words加入”b”时，最长词链[“a”]或[“b”]，长度1。
当words加入”ba”时，最长词链[“a”, “ba”]或[“b”, “ba”]]，长度2。
当words加入”bca”时，最长词链[“a”, “ba”, “bca”]或[“b”, “ba”, “bca”]，长度3。
当words加入”bda”时，最长词链[“a”, “ba”, “bda”]或[“b”, “ba”, “bda”]，长度3。
当words加入”bdca”时，最长词链[“a”, “ba”, “bca”, “bdca”]或[“b”, “ba”, “bca”, “bdca”]或[“a”, “ba”, “bda”, “bdca”]或[“b”, “ba”, “bda”, “bdca”]，长度4。

3.2.2 确定边界

对于原单词数组每一个单词而言，当我们还没有开始遍历寻找的时候，它们的最长词链就是它们本身，长度为1。

3.2.3 找规律，确定最优子结构

对于每一个words[i]，如果原数组存在它们的前身words[j]，那么它们的一个字链就是它们前身words[j]的字链加上它们自己words[i]。最长子链就是其中最长的一个。

得到最优子结构

最长子链(words[i]) = max(words[j]) + words[i]; words[j]是words[i]的前身

3.2.4 写出状态转移方程

为了保证在遍历原数组时，是按照从原单词数组中长度最短的单词开始，向长度最长的单词的顺序遍历的，我们需要先对原数组进行排序。

我们设立dp数组保存words单词数组每一个单词的最长子链的长度，得到状态转移方程。

dp[i] = max(dp[j]) + 1; 0 <= j < i, dp[j]是dp[i]的前身

在这个方程中，为了找到dp[i]的前身dp[j]，我们需要对words[i]每次挨个减少一个字母得到它的所有前身，然后遍历原单词数组words[i]前面的部分来确定这个前身是否存在，然后才进行操作。这当然是很麻烦的，当单词变长时，所需时间也会直线上升。那么，我们有没有办法简化这一过程呢。

有，使用哈希表来储存每个单词的最长子链长度，将单词本身作为关键值。这样我们直接使用words[i]的所有前身访问哈希表，就能同时完成确定这个前身否存在和对其进行操作两个任务。

在使用哈希表的前提下，重写状态转移方程。

dp[words[i]] = max(dp[word]) + 1; word是words[i]的所有前身

3.2.5 代码

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        unordered_map<string, int> cnt;
        sort(words.begin(), words.end(), [](const string a, const string b) {
            return a.size() < b.size();
        });
        int res = 0;
        for (string word : words) {
            cnt[word] = 1;
            for (int i = 0; i < word.size(); i++) {
                string prev = word.substr(0, i) + word.substr(i + 1, word.size());
                if (cnt[prev]) {
                    cnt[word] = max(cnt[prev] + 1, cnt[word]);
                }
            }
            res = max(cnt[word], res);
        }
        return res;
    }
};

原文链接：https://blog.csdn.net/m0_63852285/article/details/130541116