【九】【C语言\动态规划】139. 单词拆分(LeetCode)、467. 环绕字符串中唯一的子字符串(LeetCode)、300. 最长递增子序列(LeetCode),三道题目深度解析

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

139. 单词拆分 - 力扣(LeetCode)(C++实现)

题目解析

状态表示

状态表示通常由经验+题目要求得到。

经验一般是指,以某个位置为结尾或者以某个位置为开始。

我们很容易可以定义这样一个状态表示,定义dp[i]表示,s字符串中,下标0到下标i这段字符串,是否可以进行单词划分。

状态转移方程

根据状态表示,dp[i]表示,s字符串中,下标0到下标i这段字符串,是否可以进行单词划分。

dp[i-1]表示,s字符串中,下标0到下标i-1这段字符串,是否可以进行单词划分。

我们思考如果dp[i]为true,应该如何得到。

如果(j,i)表示一个单词,这个单词能够在wordDirt中被找到,且(0,j-1)可以进行单词划分,则表示(0,i)可以进行单词划分。

根据这个思路,我们可以将(0,i)部分划分为两个部分,

  1. (0,j-1)子串

  2. (j,i)子串

如果(j,i)能够在wordDirt中被找到,dp[i]=dp[j-1]。

因此我们填写dp[i]需要让j遍历(0,i)。

故,当我们在从 0 ~ i 枚举 j 的时候,只要 dp[j - 1] = true ,

并且后面部分的子串 s.substr(j, i - j + 1) 能够在字典中找到,那么 dp[i] = true 。

我们判断(j,i)单词是否可以被找到时,可以用hash表进行优化,将wordDirt中所有的单词都存放在hash表中,当我们需要判断(j,i)单词是否可以被找到的时候,只需要访问hash表即可。

 
unordered_set<string> hash;
        for (auto& s : wordDict)
            hash.insert(s);
            
            hash.count(s.substr(j, i - j + 1))

故状态转移方程为,

 
for (int i = 1; i <= n; i++) // 填 dp[i]
        {
            for (int j = i; j >= 1; j--) //最后一个单词的起始位置
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)) {
                    dp[i] = true;
                    break; 
                }
            }
        }

初始化

根据状态转移方程,我们推导dp[i]时,需要用到dp[j-1], j∈(0,i),

所以我们需要保证推导i位置状态时,(0,i-1)的状态全部填写完毕。

所以我们需要初始化第一个位置的状态。

如果我们初始化第一个位置的状态,我们发现需要遍历wordDirt,看能不能找到第一个元素,这个过程很是有点复杂的。因此我们可以添加一个虚拟节点,将初始化第一个位置的状态转化为初始化虚拟节点的位置。

添加虚拟节点有两点注意事项,

  1. 需要保证后续的填表不会出错,也就是初始化虚拟节点时要保证正确性。

  2. 注意下标的映射关系。

解决方案:

  1. 保证正确性:

      原本紫色第一个位置的状态表示该单个元素能不能被找到,如果用状态转移方程推导,必须保证dp[i-1]为true。 所以我们需要对虚拟节点初始化true。

  2. 下标的映射关系:

    1. dp[i]对应s[i-1]位置的元素。

    2. s字符串中最前面添加一个空串,使得dp和s一一对应。

故初始化为,

 
        dp[0] = true;                
        s = ' ' + s; 

填表顺序

根据状态转移方程,我们推导dp[i]时,需要用到dp[j-1], j∈(0,i),

所以我们需要保证推导i位置状态时,(0,i-1)的状态全部填写完毕。

故,填表顺序应该从左往右填写。

返回值

根据状态表示,dp[i]表示,s字符串中,下标0到下标i这段字符串,是否可以进行单词划分。

结合题目意思,我们需要返回最后一个元素即dp[n]。

代码实现

 
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 优化母:将字典母母的单词存在哈希表母母
        unordered_set<string> hash;
        for (auto& s : wordDict)
            hash.insert(s);

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;                // 保证后续填表是正确的
        s = ' ' + s;                 // 使原始字符串的下标统母 +1
        for (int i = 1; i <= n; i++) // 填 dp[i]
        {
            for (int j = i; j >= 1; j--) //最后母个单词的起始位置
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break; // 优化母
                }
            }
        }
        return dp[n];
    }
};

467. 环绕字符串中唯一的子字符串 - 力扣(LeetCode)

题目解析

状态表示

状态表示通常由经验+题目意思得到。

经验一般是指,以某个位置为结尾,或者以某个位置为开始。

解决子串问题一般定义以某位置为结尾的子串....

我们可以很容易得到这样一个状态表示,定义dp[i]表示s字符串中以下标为i结尾的子串在base中出现的次数。

状态转移方程

dp[i]表示s字符串中以下标为i结尾的子串在base中出现的次数。

我们针对(s字符串中以下标为i结尾的子串)进行分析。

想一想如何通过其他位置的状态推导出i位置的状态。

这些子串分为两个部分,

  1. 只有i位置一个元素的子串

  2. 不止i位置一个元素的子串

  1. 只有i位置一个元素的子串: 这种情况下,dp[i]=1。

  2. 不止i位置一个元素的子串:

    1. 如果“s[i-1]s[i]”在base中出现, 则以i-1为结尾的子串出现次数对应的每一种情况,末尾添加s[i],就是以i为结尾的子串的出现次数,也就是dp[i-1]。 这种情况下,dp[i]=dp[i-1]。

    2. 如果“s[i-1]s[i]”在base中不出现, 这种情况下,dp[i]=0。因为我们的大前提是不止i位置一个元素,所以只能是0,不存在。

将上述情况合并,dp[i]应该存储(只有i位置一个元素的子串、不止i位置一个元素的子串)这两种情况下dp值的加和。所以在(不止i位置一个元素的子串)这种情况下的dp值都可以加上1,合并(只有i位置一个元素的子串)这种情况,即

 
    for (int i = 1; i < n; i++) {
        if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
            dp[i] = dp[i - 1] + 1;
        else
            dp[i] = 1;
    }

初始化

根据状态转移方程,我们知道想要推导出i位置的状态,需要用到i-1位置的状态,所以我们需要初始化第一个元素,即,

dp[0]=1。

填表顺序

根据状态转移方程,我们知道想要推导出i位置的状态,需要用到i-1位置的状态,当我们推导i位置的状态时,i-1位置的状态应该已经得到,所以填表顺序应该是从左往右填写。即,

从左往右。

返回值

dp[i]表示s字符串中以下标为i结尾的子串在base中出现的次数。

而题目意思要求返回s不同的非空子串在base出现的次数,dp[i]和dp[i-1]里面有可能出现重复的出现次数,所以我们还需要[去重]。

对于相同字符结尾的dp值,我们仅需保留「最大」的即可,其余dp值对应的子串都可以在最大的里面找到。

所有我们可以创建一个大小为26的数组,统计所有字符结尾的最大dp值。

最后返回「数组中所有元素的和」即可。

代码实现

 
int findSubstringInWraproundString(char* s) {
    int n = strlen(s);
    int dp[n];
    dp[0] = 1;

    int num[26];
    memset(num, 0, sizeof(num));

    for (int i = 1; i < n; i++) {
        if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
            dp[i] = dp[i - 1] + 1;
        else
            dp[i] = 1;
    }

    for (int i = 0; i < n; i++) {
        num[s[i] - 'a'] = fmax(num[s[i] - 'a'], dp[i]);
    }
    
    int count = 0;
    for (int i = 0; i < 26; i++) {
        count += num[i];
    }

    return count;
}

300. 最长递增子序列 - 力扣(LeetCode)

题目解析

状态表示

状态表示是由经验+题目要求得到的。

经验一般是指以某个位置为结尾,或者以某个位置为开始。

我们可以很容易得到这样一个状态表示,定义dp[i]表示nums字符串中以下标为i结尾的子序列,最长严格递增子序列的长度。

状态转移方程

dp[i]表示nums字符串中以下标为i结尾的子序列,最长严格递增子序列的长度。

我们针对(nums字符串中以下标为i结尾的子序列)进行分析。

想一想如何通过其他位置的状态推导出i位置的状态。

这些子序列分为两个部分,

  1. 只有i位置一个元素的子序列

  2. 不止i位置一个元素的子序列

  1. 只有i位置一个元素的子序列: 这种情况下,dp[i]=1。

  2. 不止i位置一个元素的子序列: 那么i位置元素可能跟在前面(元素值小于自己元素值的)任意位置元素的后面。 定义(0<=j<=i-1),如果nums[j]<nums[i] 那么i位置元素就可以跟在j位置元素后面。 这种情况下,dp[i]=dp[j]+1。 因为dp存储的是以i位置结尾的所有子序列中,最长严格递增子序列的长度,所以j必须遍历(0~i-1)找到最长的(dp[j]+1)然后存储。

我们dp[i]存储的值应该是(只有i位置一个元素的子序列、不止i位置一个元素的子序列)两种情况的dp值的最大值。

在(不止i位置一个元素的子序列)这种情况中,dp[i]=dp[j]+1,最小值是2,所以(只有i位置一个元素的子序列)这种情况我们放到初始化解决就可以了,初始化满足最小的限制。

状态转移方程为,

 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j])
                dp[i] = fmax(dp[i], dp[j] + 1);
        }
        ret = fmax(ret, dp[i]);
    }

初始化

根据状态转移方程,我们知道想要推导出i位置的状态需要用到(0~i-1)位置的状态,所以我们需要初始化第一个位置的状态。

即,dp[0]=1。

还有一个需要注意的点,状态转移方程中,dp[i] = fmax(dp[i], dp[j] + 1);如果dp[i]没有初始化,有可能获得一个很大的随机值,所以我们应该把dp表中的数据也初始化。

满足最小的限制,结合dp[0]=1,可以这样初始化,

 
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

填表顺序

根据状态转移方程,我们知道想要推导出i位置的状态需要用到(0~i-1)位置的状态,所以当我们推导i位置状态时,(0~i-1)位置的状态应该已经得到,所以我们应该从左往右填表,即,

从左往右。

返回值

dp[i]表示nums字符串中以下标为i结尾的子序列,最长严格递增子序列的长度。

而题目意思需要我们找到最长严格递增子序列的长度,所以我们需要遍历dp表,找到最长的状态值然后返回。

代码实现

 
int lengthOfLIS(int* nums, int numsSize) {
    int n = numsSize;

    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    int ret = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j])
                dp[i] = fmax(dp[i], dp[j] + 1);
        }
        ret = fmax(ret, dp[i]);
    }

    return ret;
}

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!