YOLOのBLOG
动态规划问题
felicx 化神
  2023 年 02 月 08 日 12:24 2023-02-08 12:24   2023 年 02 月 08 日 12:52      6.4k 字  27 分钟  

一、最大子数组和（中）

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：
$1 <= nums.length <= 10^5$
$-10^4 <= nums[i] <= 10^4$

题解1

依次遍历数组，记一个临时变量$temp = 0$，$temp += nums[i]$，如果$temp < 0$，说明到temp这个位置都是负数（不用管，因为我们要看最大和，负数肯定小于正数），所以直接让temp归0；如果$temp ≥ 0$，记录这时的最大和，同时记录flag（避免遍历玩数组全是负数），继续往下遍历；最后取记录的最大值。
另外，如果数组全是负数，就直接取最大那个负数返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int temp = 0;
    int sum = 0;
    bool flag = false;
    for (int i = 0; i < nums.size(); i++) {
      temp += nums[i];
      if (temp < 0) {
        temp = 0;
      } else {
        flag = true;
        sum = max(temp, sum);
      }
    }

    if (!flag) {
      auto maxPosition = max_element(nums.begin(), nums.end());
      sum = *maxPosition;
    }
    return sum;
  }
};

题解2

动态规划四步走。
1、状态定义：
$dp[i]$表示$nums$以$nums[i]$结尾的连续子数组的最大和
2、状态初始化：
$dp[0]$根据定义，只有1个数，一定以$nums[0]$结尾，因此$dp[0] = nums[0]$
3、状态转移方程：
根据状态的定义，由于$nums[i]$一定会被选取，并且以$nums[i]$结尾的连续子数组与以$nums[i - 1]$结尾的连续子数组只相差一个元素$nums[i]$。
假设数组$nums$的值全都严格大于0，那么一定有$dp[i] = dp[i - 1] + nums[i]$。
可是$dp[i - 1]$有可能是负数，于是分类讨论：

  • 如果$dp[i - 1] > 0$，那么可以把$nums[i]$直接接在$dp[i - 1]$表示的那个数组的后面，得到和更大的连续子数组；
  • 如果$dp[i - 1] <= 0$，那么$nums[i]$加上前面的数$dp[i - 1]$以后值不会变大。于是$dp[i]$另起炉灶，此时单独的一个$nums[i]$的值，就是$dp[i]$。

以上两种情况的最大值就是$dp[i]$的值，写出如下状态转移方程：
$$
dp[i]=\left{\begin{array}{lll}
dp[i-1]+nums[i], & \text { if } & dp[i-1]>0 \
nums[i], & \text { if } & dp[i-1] \leq 0
\end{array}\right.
$$

4、状态返回值
这个问题的输出是把所有的$dp[0]、dp[1]、……、dp[n - 1]$都看一遍，取最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int dp[n];
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
      if (dp[i - 1] >= 0) {
        dp[i] = dp[i - 1] + nums[i];
      } else {
        dp[i] = nums[i];
      }
    }
    auto maxSum = max_element(dp, dp + n);
    return *maxSum;
  }
};

二、买卖股票的最佳时机（简）

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
$1 <= prices.length <= 10^5$
$0 <= prices[i] <= 10^4$

题解1

用一个变量记录一个最低价格$minPrice$，在第i天卖出股票能得到的利润就是$prices[i]-minPrice$
我们只需要遍历一遍价格数组，求出每一天卖出股票得到的利润，取最大值$maxProfit$，同时更新最低价格$minPrice$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (auto price : prices) {
      maxProfit = max(maxProfit, price - minPrice);
      minPrice = min(minPrice, price);
    }
    return maxProfit;
  }
};

题解2

这道题是最基础的动态规划，下面讲下证明用动态规划解决。
题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用动态规划的方法来解决。
根据题目意思，有以下两个约束条件：1、不能在买入股票前卖出股票；2、最多只允许完成一笔交易。
首先先定义好现金数这个概念，买入股票手上的现金数减少，卖出股票手上的现金数增加。对于这道题，当天是否持股会影响现金数，因为持股表示你还没卖掉，不持股表示卖掉了。
所以动态规划的状态需要用到二维数组表示，一方面表示第几天，一方面表示是否持股。
动态规划四步走如下。
1、状态定义：

  • $dp[i][0]$表示第i天，不持股，手上拥有的现金数
  • $dp[i][1]$表示第i天，持股，手上拥有的现金数

2、状态初始化：
第1天，$dp[0][0] = 0$，$dp[0][1] = -prices[0]$
3、状态转移方程：
第i天，对于$dp[i][0]$，有两种情况

  • 昨天不持股，今天什么都不做
  • 昨天持股，今天卖出股票（现金数增加）

因此$dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])$
同样对于$dp[i][1]$，也有两种情况

  • 昨天持股，今天什么都不做（现金数与昨天一样）
  • 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）

因此$dp[i][1] = max(dp[i-1][1], -prices[i])$
4、状态返回值
遍历到最后一天，不持股状态下就是利润最大化的输出，即$dp[n - 1][0]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
      return 0;
    }
    // vector<vector<int>> dp(n, vector<int>(2));
    // 数据量大尽量用数组,vector操作太耗时
    int dp[n][2];

    // dp[i][0],下标为i这天结束的时候,不持股,手上拥有的现金数
    // dp[i][1],下标为i这天结束的时候,持股,手上拥有的现金数
    // 初始化:不持股显然为0,持股就需要减去第1天(下标为0)的股价
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 从第2天开始遍历
    for (int i = 1; i < n; i++) {
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      dp[i][1] = max(dp[i - 1][1], -prices[i]);
    }
    return dp[n - 1][0];
  }
};

三、买卖股票的最佳时机 II（中）

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：
$1 <= prices.length <= 3 * 10^4$
$0 <= prices[i] <= 10^4$

题解

和上一题一样，状态定义不变，只不过状态方程有点变化。
动态规划四步走如下。
1、状态定义：

  • $dp[i][0]$表示第i天，不持股，手上拥有的现金数
  • $dp[i][1]$表示第i天，持股，手上拥有的现金数

2、状态初始化：
第1天，$dp[0][0] = 0$，$dp[0][1] = -prices[0]$

3、状态转移方程：
第i天，对于$dp[i][0]$，有两种情况

  • 昨天不持股，今天什么都不做
  • 昨天持股，今天卖出股票（现金数增加）

因此$dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])$
同样对于$dp[i][1]$，也有两种情况

  • 昨天持股，今天什么都不做（现金数与昨天一样）
  • 昨天不持股，即$dp[i-1][0]$，今天买入股票（注意：允许交易多次，因此手上的现金数就是$dp[i-1][0]-prices[i]$）

因此$dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])$。
4、状态返回值
遍历到最后一天，不持股状态下就是利润最大化的输出，即$dp[n - 1][0]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
      return 0;
    }
    int dp[n][2];

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 从第2天开始遍历
    for (int i = 1; i < n; i++) {
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
  }
};

四、买卖股票的最佳时机 III（困）

题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：
输入：prices = [1]
输出：0

提示：
$1 <= prices.length <= 10^5$
$0 <= prices[i] <= 10^5$

题解

分析步骤参照第二题，但这道题状态比第二题多。一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过
所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]
动态规划四步走如下。
1、状态定义：

  • $dp[i][0][0]$表示第i天，不持股，不卖出过股票，手上拥有的现金数
  • $dp[i][0][1]$表示第i天，不持股，卖出1次股票，手上拥有的现金数
  • $dp[i][0][2]$表示第i天，不持股，卖出2次股票，手上拥有的现金数
  • $dp[i][1][0]$表示第i天，持股，不卖出过股票，手上拥有的现金数
  • $dp[i][1][1]$表示第i天，持股，卖出1次股票，手上拥有的现金数
  • $dp[i][1][2]$表示第i天，持股，卖出2次股票，手上拥有的现金数

2、状态初始化：
第1天有，

  • 第1天休息：$dp[0][0][0] = 0$
  • 第1天买入：$dp[0][1][0] = -prices[0]$
  • 第1天不可能已经有卖出：$dp[0][0][1] = float(‘-inf’)$、$dp[0][0][2] = float(‘-inf’)$
  • 第一天不可能已经卖出：$dp[0][1][1] = float(‘-inf’)$、$dp[0][1][2] = float(‘-inf’)$

3、状态转移方程：
第i天有，

  • 对于$dp[i][0][0]$，有一种情况，未持股，未卖出过，说明从未进行过买卖。
    因此$dp[i][0][0] = 0$
  • 对于$dp[i][0][1]$，有两种情况，未持股，卖出过1次，可能是之前卖的，可能是今天卖的。因此$dp[i][0][1]=max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])$
  • 对于$dp[i][0][2]$，有两种情况，未持股，卖出过2次，可能是之前卖的，可能是今天卖的。因此$dp[i][0][2]=max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])$
  • 对于$dp[i][1][0]$，有两种情况，持股，未卖出过，可能是之前买的，可能是今天买的。因此$dp[i][0][1]=max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])$
  • 对于$dp[i][1][1]$，有两种情况，持股，卖出过1次，可能是之前买的，可能是今天买的。因此$dp[i][0][1]=max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])$
  • 对于$dp[i][1][2]$，有一种情况，持股，卖出过2次，不可能（因为最多只允许买卖两次）。因此$dp[i][1][2]=float(‘-inf’)$

4、状态返回值
遍历到最后一天，不持股状态下取卖出1次和卖出2次的最大值，即$max(max(dp[n - 1][0][1], dp[n - 1][0][2]), 0)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
      return 0;
    }
    int MIN_VALUE = INT_MIN / 2;
    // 这里除2是因为最小值加上1就变成最大值了,会影响max()函数的结果,除数只要比1大就行
    int dp[n][2][3];

    dp[0][0][0] = 0;           // 第一天休息
    dp[0][1][0] = -prices[0];  // 第一天买入
    dp[0][0][1] = MIN_VALUE;   // 第一天不可能已经有卖出
    dp[0][0][2] = MIN_VALUE;   // 第一天不可能已经卖出
    dp[0][1][1] = MIN_VALUE;
    dp[0][1][2] = MIN_VALUE;

    // 从第2天开始遍历
    for (int i = 1; i < n; i++) {
      dp[i][0][0] = 0;  // 未持股，未卖出过
      dp[i][0][1] = max(dp[i - 1][1][0] + prices[i],
                        dp[i - 1][0][1]);  // 未持股，卖出过1次
      dp[i][0][2] = max(dp[i - 1][1][1] + prices[i],
                        dp[i - 1][0][2]);  // 未持股，卖出过2次
      dp[i][1][0] =
          max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);  // 持股，未卖出过
      dp[i][1][1] =
          max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);  // 持股，卖出过1次
      dp[i][1][2] = MIN_VALUE;  // 持股，卖出过2次
    }
    return max(max(dp[n - 1][0][1], dp[n - 1][0][2]), 0);
  }
};

五、最长回文子串（中）

题目

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

题解1

对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
例如对于字符串“ababa”，如果我们已经知道“bab” 是回文串，那么“ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
因此，如果$dp[left][right]$是回文，我们要判断$dp[left-1][right+1]$是否为回文。只需要判断字符串在$left-1$和$right+1$两个位置是否为相同的字符，就能减少了很多重复计算。
动态规划四步走如下。
1、状态定义：
$dp[left][right]$表示区间范围$[left,right]$的子串是否是回文子串
2、状态初始化：
根据定义，所有长度为1的子串都是回文串，即

1
2
3
for (int i = 0; i < sLen; i++) {
  dp[i][i] = true;
}

3、状态转移方程：
在确定转移方程时，就要分析如下几种情况。
整体上是两种，就是$s[left]$与$s[right]$相等和不相等两种情况。
当$s[left]$与$s[right]$不相等，那没啥好说的了，$dp[left][right]$一定是false。
当$s[left]$与$s[right]$相等时，这就复杂一些了，有如下三种情况:

  • 下标$left$与$right$相同，是同一个字符，例如a，当然是回文子串
  • 下标$left$与$right$相差在2以内，例如aa或aba，也是回文子串
  • 下标$left$与$right$相差大于2的时候，例如cabac，此时$s[left]$与$s[right]$已经相同了，我们看$[left,right]$区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是$[left+1,right-1]$区间，这个区间是不是回文就看$dp[left + 1][right - 1]$是否为true。

那么状态转移方程就是

1
2
3
if ((s[left] == s[right]) && (right - left <= 2 || dp[left + 1][right - 1])) {
  dp[left][right] = true;
}

4、状态返回值
判断$dp[left][right]$是否为回文，是就记录回文长度和起始位置，根据这俩就能输出最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  string longestPalindrome(string s) {
    int sLen = s.size();
    if (sLen < 2) {
      return s;
    }
    int maxLen = 1, start = 0;
    int dp[sLen][sLen];
    for (int i = 0; i < sLen; i++) {
      // 初始化,所有长度为1的子串都是回文串
      dp[i][i] = true;
    }
    for (int subLen = 2; subLen <= sLen; subLen++) {
      for (int left = 0; left < sLen; left++) {
        int right = subLen + left - 1;  // // 由subLen和left可以确定右边界
        if (right >= sLen) {
          // 如果右边界越界,就可以退出当前循环
          break;
        }
        if ((s[left] == s[right]) &&
            (right - left <= 2 || dp[left + 1][right - 1])) {
          dp[left][right] = true;
        } else {
          dp[left][right] = false;
        }
        if (dp[left][right] && right - left + 1 > maxLen) {
          maxLen = right - left + 1;
          start = left;
        }
      }
    }
    return s.substr(start, maxLen);
  }
};

题解2

因为回文串是对称的，这道题推荐用中心扩散法。
顾名思义，从每一个位置出发，向两边扩散，遇到不是回文的时候结束。
所以可以对每个字符进行扩散，以字符为中心点，$left$为中心点-1，$right$为中心点+1，有三种情况：
1、$left$没有超出左边界同时与中心点相等，继续向左扩展
2、$right$没有超出右边界同时与中心点相等，继续向右扩展
3、$left$和$right$都没超出边界，且$left$的字符等于$right$的字符，两边同时扩散
另外，题目要输出的是子串，所以要记录$left$的位置和最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  string longestPalindrome(string s) {
    int sLen = s.size();
    if (sLen == 0) {
      return "";
    }
    int left = 0, right = 0, maxLen = 0, start = 0;
    for (int i = 0; i < sLen; i++) {
      int len = 1;
      left = i - 1;   // 取中心点左边
      right = i + 1;  // 取中心点右边
      while (left >= 0 && s[left] == s[i]) {
        // 没有超过左边界同时与中心点相等,继续向左扩展
        left--;
        len++;
      }
      while (right < sLen && s[right] == s[i]) {
        // 没有超过右边界同时与中心点相等,继续向右扩展
        right++;
        len++;
      }
      while (left >= 0 && right < sLen && s[left] == s[right]) {
        // 没有超过边界同时左右点都与中心点相等,两边都扩展
        // 这里要注意, 在最后一次循环中left还是做了
        // -1操作,实际上子串不包含这个位置, 所以下面start=left+1
        left--;
        right++;
        len += 2;
      }
      if (len > maxLen) {
        maxLen = len;
        start = left + 1;
      }
    }
    return s.substr(start, maxLen);
  }
};

六、最长递增子序列（中）

题目

给你一个整数数组 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

示例 3：
输入：$nums = [7,7,7,7,7,7,7]$
输出：1

提示：
$1 <= nums.length <= 2500$
$-10^4 <= nums[i] <= 10^4$

题解

动态规划四步走如下：
1、状态定义：
$dp[i]$表示$nums$中以$nums[i]$结尾的最长子序列长度
2、状态初始化：
$dp[i]$所有元素置1，含义是每个元素都至少可以单独成为子序列，此时长度都为1
3、状态转移方程：
设$j∈[0,i)$，考虑每轮计算新$dp[i]$时，遍历$[0,i)$列表区间，做以下判断：

  • 当$nums[i] > nums[j]$时：$nums[i]$可以接在$nums[j]$之后（此题要求严格递增），此情况下最长上升子序列长度为$dp[j] + 1$；
    • 这种情况下计算出的$dp[j] + 1$的最大值，为直到$i$的最长上升子序列长度（即$dp[i]$）；
    • 实现方式为遍历$j$时，每轮执行$dp[i] = max(dp[i], dp[j] + 1)$
  • 当$nums[i] <= nums[j]$时：$nums[i]$无法接在$nums[j]$之后，此情况上升子序列不成立，跳过。

4、状态返回值
返回$dp$列表最大值，即可得到全局最长上升子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    int dp[n];
    dp[0] = 1;
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
      maxLen = max(dp[i], maxLen);
    }

    return maxLen;
  }
};

七、最长公共子序列（中）

题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

题解

动态规划四步走如下：
1、状态定义：
$dp[i][j]$表示$text1[0:i]$和$text2[0:j]$的最长公共子序列的长度。
2、状态初始化：
初始化就是要看当$i=0$与$j=0$时，$dp[i][j]$应该取值为多少。很显然，当$text1$或$text2$为空时，它们的最长公共子序列长度为0。
所以，当$i=0$或$j=0$时，$dp[i][j]$初始化为0。
3、状态转移方程：

  • 当$text1[i-1]=text2[j-1]$时，说明两个子字符串的最后一位相等，所以最长公共子序列增加1，即$dp[i][j]=dp[i-1][j-1]+1$；
  • 当$text1[i-1]!=text2[j-1]$时，说明两个子字符串的最后一位不相等，那么此时的状态$dp[i][j]$应该是$dp[i-1][j]$和$dp[i][j-1]$中的较大值；
    • 比如对于$ace$和$bc$而言，他们的最长公共子序列的长度等于①$ace$和$b$的最长公共子序列长度0与②$ac$和$bc$的最长公共子序列长度1的最大值，即1。

4、状态返回值
返回$dp[s1][s2]$，即$text1$和$text2$的最长公共子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int longestCommonSubsequence(string text1, string text2) {
    int s1 = text1.size();
    int s2 = text2.size()
    int dp[s1 + 1][s2 + 1];
    // 初始化
    for (int i = 0; i <= s1; i++) {
      for (int j = 0; j <= s2; j++) {
        dp[i][j] = 0;
      }
    }
    // 状态转移方程
    for (int i = 1; i <= s1; i++) {
      for (int j = 1; j <= s2; j++) {
        if (text1[i - 1] == text2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[s1][s2];
  }
};
动态规划问题
1625968864.html
作者
felicx
发布于
2023-02-08 12:24
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 一、最大子数组和（中）
    1. 题目
    2. 题解1
    3. 题解2
  2. 二、买卖股票的最佳时机（简）
    1. 题目
    2. 题解1
    3. 题解2
  3. 三、买卖股票的最佳时机 II（中）
    1. 题目
    2. 题解
  4. 四、买卖股票的最佳时机 III（困）
    1. 题目
    2. 题解
  5. 五、最长回文子串（中）
    1. 题目
    2. 题解1
    3. 题解2
  6. 六、最长递增子序列（中）
    1. 题目
    2. 题解
  7. 七、最长公共子序列（中）
    1. 题目
    2. 题解
© 2018 - 2024    felicx
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. 一、最大子数组和（中）
    1. 题目
    2. 题解1
    3. 题解2
  2. 二、买卖股票的最佳时机（简）
    1. 题目
    2. 题解1
    3. 题解2
  3. 三、买卖股票的最佳时机 II（中）
    1. 题目
    2. 题解
  4. 四、买卖股票的最佳时机 III（困）
    1. 题目
    2. 题解
  5. 五、最长回文子串（中）
    1. 题目
    2. 题解1
    3. 题解2
  6. 六、最长递增子序列（中）
    1. 题目
    2. 题解
  7. 七、最长公共子序列（中）
    1. 题目
    2. 题解