动态规划问题

一、最大子数组和（中）

题目

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

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

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、状态定义：
表示以结尾的连续子数组的最大和
2、状态初始化：
根据定义，只有1个数，一定以结尾，因此
3、状态转移方程：
根据状态的定义，由于一定会被选取，并且以结尾的连续子数组与以结尾的连续子数组只相差一个元素。
假设数组的值全都严格大于0，那么一定有。
可是有可能是负数，于是分类讨论：

如果，那么可以把直接接在表示的那个数组的后面，得到和更大的连续子数组；
如果，那么加上前面的数以后值不会变大。于是另起炉灶，此时单独的一个的值，就是。

以上两种情况的最大值就是的值，写出如下状态转移方程：
$$
dp[i]=\left{\right.
$$

4、状态返回值
这个问题的输出是把所有的 $、、、$ 都看一遍，取最大值

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

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

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、状态定义：

表示第i天，不持股，手上拥有的现金数
表示第i天，持股，手上拥有的现金数

2、状态初始化：
第1天，，
3、状态转移方程：
第i天，对于，有两种情况

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

因此
同样对于，也有两种情况

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

因此
4、状态返回值
遍历到最后一天，不持股状态下就是利润最大化的输出，即

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、状态定义：

表示第i天，不持股，手上拥有的现金数
表示第i天，持股，手上拥有的现金数

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

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

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

因此
同样对于，也有两种情况

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

因此。
4、状态返回值
遍历到最后一天，不持股状态下就是利润最大化的输出，即

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次、可能卖出过2次、也可能未卖出过
所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]
动态规划四步走如下。
1、状态定义：

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

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

第1天休息：
第1天买入：
第1天不可能已经有卖出：、
第一天不可能已经卖出：、

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

对于，有一种情况，未持股，未卖出过，说明从未进行过买卖。
因此
对于，有两种情况，未持股，卖出过1次，可能是之前卖的，可能是今天卖的。因此
对于，有两种情况，未持股，卖出过2次，可能是之前卖的，可能是今天卖的。因此
对于，有两种情况，持股，未卖出过，可能是之前买的，可能是今天买的。因此
对于，有两种情况，持股，卖出过1次，可能是之前买的，可能是今天买的。因此
对于，有一种情况，持股，卖出过2次，不可能（因为最多只允许买卖两次）。因此

4、状态返回值
遍历到最后一天，不持股状态下取卖出1次和卖出2次的最大值，即

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”。
因此，如果是回文，我们要判断是否为回文。只需要判断字符串在和两个位置是否为相同的字符，就能减少了很多重复计算。
动态规划四步走如下。
1、状态定义：
表示区间范围的子串是否是回文子串
2、状态初始化：
根据定义，所有长度为1的子串都是回文串，即

1
2
3

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

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

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

那么状态转移方程就是

1
2
3

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

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

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

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

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：
输入：
输出：4
解释：最长递增子序列是，因此长度为 4 。

示例 2：
输入：
输出：4

示例 3：
输入：
输出：1

提示：

题解

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

当时：可以接在之后（此题要求严格递增），此情况下最长上升子序列长度为；
- 这种情况下计算出的的最大值，为直到的最长上升子序列长度（即）；
- 实现方式为遍历时，每轮执行
当时：无法接在之后，此情况上升子序列不成立，跳过。

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

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、状态定义：
表示和的最长公共子序列的长度。
2、状态初始化：
初始化就是要看当与时，应该取值为多少。很显然，当或为空时，它们的最长公共子序列长度为0。
所以，当或时，初始化为0。
3、状态转移方程：

当时，说明两个子字符串的最后一位相等，所以最长公共子序列增加1，即；
当时，说明两个子字符串的最后一位不相等，那么此时的状态应该是和中的较大值；
- 比如对于和而言，他们的最长公共子序列的长度等于①和的最长公共子序列长度0与②和的最长公共子序列长度1的最大值，即1。

4、状态返回值
返回，即和的最长公共子序列长度

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];
  }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

请作者喝杯咖啡吧