【LeetCode】动态规划 刷题训练(九)

文章目录

• 环绕字符串中唯一的子字符串
• • 题目解析
  • 状态转移方程
  • 返回值
  • 完整代码
• 最长递增子序列
• • 子数组与子序列的区别
  • 状态转移方程
  • 完整代码
• 摆动序列
• • 题目解析
  • 状态转移方程
  • • f[i]状态转移方程
    • g[i]状态转移方程
  • 完整代码

环绕字符串中唯一的子字符串

点击查看:467. 环绕字符串中唯一的子字符串

定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串，所以 base 看起来是这样的：
“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

示例 1：
输入：s = “a”
输出：1
解释：字符串 s 的子字符串 “a” 在 base 中出现。
示例 2：
输入：s = “cac”
输出：2
解释：字符串 s 有两个子字符串 (“a”, “c”) 在 base 中出现。

题目解析

若以c开头，则可分为 c ca cac
若以a开头，则可分为 a ac
若以最后一个c开头，则可分为c

在环绕字符串中去寻找 上述六种字符串，发现只有 c a 符合要求
所以只有两种

状态转移方程

dp[i] 表示 以i位置的元素为结尾的所有的子串里面，有多少个在base中出现过

dp[i]分为两种情况

–

情况1：i位置元素本身(长度为1)
在base中包含a-z的所有字母，所以单独一个字母肯定在base中出现
即该情况下长度为1

情况2：i位置元素与前面元素结合(长度大于1)

想要求以i位置的元素为结尾的所有的子串里面，有多少个在base中出现过
就需要先求i-1位置的元素为结尾的所有的子串里面，有多少个在base中出现 即dp[i-1]
然后再加上i位置的元素即可
需要保证以 i-1位置为结尾的子串加上i位置元素也要在base中出现

情况1：base是由a到z连续组成
由i-1位置的字符ASCII值+1 即可为i位置的字符的ASCII值 即s[i-1]+1==s[i]

情况2：base是由z到a 跳跃组成
i-1位置的字符为z，i位置的字符为a 即s[i-1]==‘z’ && s[i] ==‘a’

两种情况满足一个时，才为符合条件的子字符串

返回值

对于上述字符串，若返回值计算的是dp表的所有值之和
则会计算重复的子串ac ca ,导致结果错误
所以需要去重

两个字符串都是以d字符为结尾的，若都计算就会造成重复
所以当相同字符结尾，将dp值较大的进行累加 ，将dp值较小的舍去

完整代码

class Solution {
public:
    int findSubstringInWraproundString(string s) {
          int n=s.size();
          //在base中包含a-z的所有字母，所以单独一个字母肯定在base中出现
          //所以将dp表初始化为1
          vector<int>dp(n,1);
         //创建大小为26的数组，用于统计以i位置2为结尾的dp值
         //将dp值大的进行累加 将dp值小的舍去
         //以此达到去重
         vector<int>arr(26,0);
          int i=0;
          int ret=0;
          for(i=1;i<n;i++)
          {
              if(s[i-1]+1==s[i]||s[i-1]=='z'&&s[i]=='a')
              {
                  dp[i]+=dp[i-1];
              }
          }
          //遍历dp表 取其中重复子串的dp最大值
          for(i=0;i<n;i++)
          {
              arr[s[i]-'a']=max(arr[s[i]-'a'],dp[i]);
          }
          for(auto&e:arr)
          {
              ret+=e;
          }
          //返回arr数组的和
          return ret; 
    }
};

最长递增子序列

点击查看:300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

子数组与子序列的区别

子序列：按照从左到右的顺序，任意挑选几个 所组成的新序列 即为子序列
如：a b d 为子序列 跳过了c ，但相对顺序与原数组保持一致(d在原数组中就在a b后，新的数组也是如此)
而 d a b 就不是一个子序列了

子数组：按照从左到右的顺序，任意挑选的必须是连续的
如：a b c为子数组 ，但 a b d就不是子数组

状态转移方程

dp[i] 表示 以i位置元素为结尾的所有的子序列中，最长的递增子序列的长度

dp[i]分为两种情况

情况1：i位置元素本身(长度为1)
只有i位置元素本身，所以该情况下最长的递增子序列的长度为1

情况2：i位置元素和前面元素结合(长度大于1)