【Leetcode刷题】动态规划_leetcode动态规划

本篇文章为LeetCode 动态规划模块的刷题笔记，仅供参考。

动态规划是一种常用的优化手段，以空间换时间达到降低时间复杂度的目的。使用动态规划必须满足以下几个必要条件：

• 重叠子问题：动态规划比暴力搜索的优越性在于 dp 通过记录子问题的最优解节省了重叠子问题的计算时间，因此动态规划一般是从小规模问题开始计算；
• 最优子结构：问题的最优解必须由子问题的最优解组成，这样才能够保证每一次递推最优解的合理性；
• 子问题不相关：其实前两个条件贪心算法可能也具有，但贪心算法在选择最优解时可能忽略了子问题的相关性而选择了局部最优解。比如无权最长路径问题，由于无环的限制，不同子问题之间路径选择有一定的互斥性，即子问题相关，因此无法使用动态规划解决。

动态规划之前，需要 确定状态数组，可以是一维，也可以是二维。一维数组适用于序列可以从 0 开始向后递推，如最大子数组和、解码方法等；二维数组适用于序列可以被从中间截取的（如最长回文子串）、状态机（如买卖股票的最佳时机）、两个序列交错（如交错字符串）等问题。需要注意的是，无论是一维数组还是二维数组，都需要理清是否包括长度为 0 的序列（见交错字符串思路），这关系到状态数组的大小，是 dp[n] 还是 dp[n+1]。有时状态较多需要分类讨论，可以使用不止一个状态数组，如乘积最大子数组、打家劫舍III 等。

动态规划的核心就是状态转移方程和边界控制。思考状态转移方程时，我们一般根据题干所给序列 选取一个元素作为一个小问题，再思考如何 将其与前或后元素拼接得到大问题的最优解，然后逐步确定状态转移方程。边界控制其实就是小问题的解，由人为指定。

Leetcode5.最长回文子串

Leetcode5.最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

用数组 dp[i][j] 表示 s[i…j] 是否是回文子串，有递推表达式：

if(i>j)	dp[i][j]=false;
else if(i==j)	dp[i][j]=true;
else if(i==j-1){
	if(s[i]==s[j])	dp[i][j]=true;
	else	dp[i][j]=false;
}
else	dp[i][j]=dp[i+1][j-1] && s[i]==s[j];
1
2
3
4
5
6
7

需要注意的是：

1. dp数组如果用 vector 存储的话，需要事先指定大小：

vector<vector<bool> > dp;
vector<bool> tmp(n);
dp.resize(n,tmp);
1
2
3

2. 不能直接内外层循环 for i from 0 to n-1: for j from 0 to n-1 遍历 s[i…j]，因为 dp[i][j] 依赖于 dp[i+1][j-1]，所以循环最外层要按 s[i…j] 长度由短到长才行。

代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int Max_len=0;
        string ans="";
        int n=s.length();
        vector<vector<bool> > dp;
        vector<bool> tmp(n);
        dp.resize(n,tmp);
        for(int len=1;len<=n;len++){
            for(int i=0;i<=n-len;i++){
                int j=i+len-1;
                if(len==1){
                    dp[i][j]=true;
                    if((len)>Max_len){
                        Max_len=len;
                        ans=s.substr(i,Max_len);
                    }
                }
                else if(len==2){
                    if(s[i]==s[j]){
                        dp[i][j]=true;
                        if(len>Max_len){
                            Max_len=len;
                            ans=s.substr(i,Max_len);
                        }
                    }
                    else	dp[i][j]=false;
                }
                else{
                    dp[i][j]=dp[i+1][j-1] && (s[i]==s[j]);
                    if(dp[i][j] && len>Max_len){
                        Max_len=len;
                        ans=s.substr(i,Max_len);
                    }
                }
            }
        }
        return ans;
    }
};
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
39
40
41

Leetcode62.不同路径

Leetcode62.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：

输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示： 1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10⁹

法一：动态规划，用 path[i][j] 表示从起点到 (i, j) 的不同路径数，则有递推表达式：

if(i==0 || j==0)	path[i][j]=1;
else	path[i][j]=path[i-1][j]+path[i][j-1];
1
2

代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > path;
        vector<int> tmp(n);
        path.resize(m,tmp);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 || j==0)	path[i][j]=1;
                else	path[i][j]=path[i-1][j]+path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

法二：其实本题有较强的数学背景：从起点到终点，需要向右 n-1 格，向下移动 m-1 格，则路径为 n-1 步与 m-1 步的组合问题，即答案为组合数 C(m+n-2)(n-1)

需要注意的是：为了防止乘法溢出，用 long 型变量，并且在计算阶乘的过程中不断除以公因数：

class Solution {
public:
    int uniquePaths(int m, int n) { //C(m+n-2)(n-1)
        long tmp1=1;
        long tmp2=1;
        for(int i=m;i<=n+m-2;i++){
            tmp1*=i;
            tmp2*=(i-m+1);
            int gcd=__gcd(tmp1,tmp2);
            tmp1/=gcd;
            tmp2/=gcd;
        }
        return tmp1/tmp2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Leetcode63.不同路径 II

Leetcode63.不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m = obstacleGrid.length
n = obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

将障碍处的 path 值置为 0 即可：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int> > path;
        vector<int> tmp(n);
        path.resize(m,tmp);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(obstacleGrid[i][j])  path[i][j]=0;
                else if(i==0 && j==0)   path[i][j]=1;
                else if(i==0)	path[i][j]=path[0][j-1];
                else if(j==0)	path[i][j]=path[i-1][0];
                else	path[i][j]=path[i-1][j]+path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Leetcode121.买卖股票的最佳时机

Leetcode121.买卖股票的最佳时机
给定一个数组 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⁵
0 <= prices[i] <= 10⁴

根据利润公式：当天的最大利润 = 当天价格 - 前几天的最低价；因此有 Max_profit = max(price[i]-Min_price, Max_profit)：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int Max_profit=0;
        int Min_price=INT_MAX;
        for(int i=0;i<n;i++){
            Max_profit=max(Max_profit,prices[i]-Min_price);
            Min_price=min(prices[i],Min_price);
        }
        return Max_profit;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

Leetcode122.买卖股票的最佳时机 II

Leetcode122.买卖股票的最佳时机 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⁴
0 <= prices[i] <= 10⁴

因为可以多次交易且每天最多持有一股，因此第 i 天买入第 j 天卖掉 等价于 第 i 天买入后每天买了再卖直至第 j 天。因此遍历数组，每天价格只要比前一天低就前一天买入今天卖出，否则不交易：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int Max_profit=0;
        for(int i=1;i<n;i++){
            if(prices[i]>prices[i-1]){
                Max_profit+=(prices[i]-prices[i-1]);
            }
        }
        return Max_profit;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

Leetcode123.买卖股票的最佳时机 III

Leetcode123.买卖股票的最佳时机 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⁵
0 <= prices[i] <= 10⁵

• Leetcode121 中只能交易一次，因此遍历 prices 数组中只维护 2 个状态 {Min_price, Max_profit}，通过赋值改变；
• Leetcode122 中可以交易无数次，因此遍历 prices 数组时有 n 个状态，通过累加改变；
• Leetcode123 中只能交易两次，因此需要有相应的几个状态相互转化：最少买卖各 0 次，最多买卖各 2 次，则有 5 种状态。记：

1. S0[i] 表示到第 i 天 0 买 0 卖的最大利润；
2. S1[i] 表示到第 i 天 1 买 0 卖的最大利润；
3. S2[i] 表示到第 i 天 1 买 1 卖的最大利润；
4. S3[i] 表示到第 i 天 2 买 1 卖的最大利润；
5. S4[i] 表示到第 i 天 2 买 2 卖的最大利润，

并且 5 种状态可以相互转化：

//第i天0买0卖只能是前一天也0买0卖
S0[i]=S0[i-1]
//第i天1买0卖可能是前一天1买0卖,也可能是前一天0买0卖今天1买
S1[i]=max(S1[i-1],S0[i-1]-prices[i])
//第i天1买1卖可能是前一天1买1卖,也可能是前一天1买0卖今天1卖
S2[i]=max(S2[i-1],S1[i-1]+prices[i])
//第i天2买1卖可能是前一天2买1卖,也可能是前一天1买1卖今天1买
S3[i]=max(S3[i-1],S2[i-1]-prices[i])
//第i天2买2卖可能是前一天2买2卖,也可能是前一天2买1卖今天1卖
S4[i]=max(S4[i-1],S3[i-1]+prices[i])
1
2
3
4
5
6
7
8
9
10

需要注意初值的选取：因为题目限定的是交易次数不超过两次，于是将同一天买了再卖股票视为有效交易次数。因此最终的 S4[n-1] 则为 2买2卖 交易的最大利润（实际上其中有可能某一天同时买卖，也就是实际交易次数可能为 1 次甚至 0 次交易）。于是 S1[0] 和 S3[0] 的初值需要赋为 -prices[0]。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> S0(n);
        vector<int> S1(n);
        vector<int> S2(n);
        vector<int> S3(n);
        vector<int> S4(n);
        S1[0]=-prices[0];
        S3[0]=-prices[0];
        for(int i=1;i<n;i++){
            //第i天0买0卖只能是前一天也0买0卖
            S0[i]=S0[i-1];
            //第i天1买0卖可能是前一天1买0卖,也可能是前一天0买0卖今天1买
            S1[i]=max(S1[i-1],S0[i-1]-prices[i]);
            //第i天1买1卖可能是前一天1买1卖,也可能是前一天1买0卖今天1卖
            S2[i]=max(S2[i-1],S1[i-1]+prices[i]);
            //第i天2买1卖可能是前一天2买1卖,也可能是前一天1买1卖今天1买
            S3[i]=max(S3[i-1],S2[i-1]-prices[i]);
            //第i天2买2卖可能是前一天2买2卖,也可能是前一天2买1卖今天1卖
            S4[i]=max(S4[i-1],S3[i-1]+prices[i]);
        }
        return S4[n-1];
    }
};
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

Leetcode188.买卖股票的最佳时机 IV

Leetcode188.买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

思路同 Leetcode123，有 2k+1 个状态互相转化，转移方程为：

if(j%2==1){	//奇数次交易，即买的次数比卖的次数多1
	S[j][i]=max(S[j-1][i-1]-prices[i],S[j][i-1]);
}else{		//偶数次交易
	S[j][i]=max(S[j-1][i-1]+prices[i],S[j][i-1]);
}
1
2
3
4
5

其中 i 是天数，j 是状态。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<=1)    return 0;
        vector<vector<int>> S;
        vector<int> tmp(n);
        S.resize(2*k+1,tmp);
        for(int i=0;i<=2*k;i++){
            if(i%2==1)  S[i][0]=-prices[0];
        }
        for(int i=1;i<n;i++){           //i是天数
            S[0][i]=S[0][i-1];
            for(int j=1;j<=2*k;j++){    //j是状态
                if(j%2==1){     //奇数次交易，即买的次数比卖的次数多1
                    S[j][i]=max(S[j-1][i-1]-prices[i],S[j][i-1]);
                }else{          //偶数次交易
                    S[j][i]=max(S[j-1][i-1]+prices[i],S[j][i-1]);
                }
            }
        }
        return S[2*k][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Leetcode309.最佳买卖股票时机含冷冻期

Leetcode309.最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000

仍采用 状态机 的思想，很多题解通过状态合并只保留 3 个状态，不容易理解。此处一共有 4 种状态：手中持有股票、刚卖掉股票、处于冷冻期、冷冻期结束可以随意买卖。记：

1. S0[i] 表示第 i 天手中持有 1 支股票的最大利润；
2. S1[i] 表示到第 i 天卖掉手中股票的最大利润；
3. S2[i] 表示到第 i 天处于冷冻期的最大利润；
4. S3[i] 表示到第 i 天冷冻期结束可以随意买卖的最大利润。

注意此处冷冻期只有 1 天，即 卖掉股票后经历的 24 小时。可能不太好理解，不妨假定每日交易时间为凌晨 0 点整，即交易完正好开启新的状态！否则第 i 天交易时刻前后划分了两个状态还不好分析。在假定凌晨 0 点进行交易的前提下，有状态转移方程：

$\uparrow$ 一开始按 3 个状态考虑的混乱思路，纯凑答案，最后还把自己绕晕了 $\uparrow$

有状态转移方程：

//今天手中持有股票可能是昨天就有的（昨天手中持有1支股票）或者今天买的（昨天处于冷冻期或者自由交易状态）
S0[i]=max(S0[i-1],S2[i-1]-prices[i],S3[i-1]-prices[i]);
//今天卖股票只能是昨天手中有1支股票
S1[i]=S0[i-1]+prices[i];
//今天处于冷冻期只能是昨天卖了股票
S2[i]=S1[i-1],
//今天可以自由交易可以是昨天处于冷冻期或者昨天就可以自由交易
S3[i]=max(S2[i-1],S3[i-1]);
1
2
3
4
5
6
7
8

代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<=1)    return 0;
        vector<int> S0(n);
        vector<int> S1(n);
        vector<int> S2(n);
        vector<int> S3(n);
        S0[0]=-prices[0];
        for(int i=1;i<n;i++){
            S0[i]=max(S0[i-1],max(S2[i-1]-prices[i],S3[i-1]-prices[i]));
            S1[i]=S0[i-1]+prices[i];
            S2[i]=S1[i-1],
            S3[i]=max(S2[i-1],S3[i-1]);
        }
        return max(max(S0[n-1],S1[n-1]),max(S2[n-1],S3[n-1]));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Leetcode53.最大子数组和

Leetcode53.最大子数组和
给你一个整数数组 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⁵
-10⁴ <= nums[i] <= 10⁴

第一反应是暴力枚举，可以通过动态规划数组加以记录 Sum[i…j] 来减轻计算的压力：

if(len==1)  dp[i][j]=nums[i];
else if(len==2) dp[i][j]=nums[i]+nums[j];
else{
    dp[i][j]=dp[i+1][j-1]+nums[i]+nums[j];
}
1
2
3
4
5

但是 O(n²) 的时间复杂度难以解决问题。像这种连续可按前缀分割的数组问题，可以用 f(i) 表示以第 i 个数结尾的连续子数组的最大和，那么最终的结果就是 max{f(i)}。下面考虑 f(i) 的状态转移方程：

对于 f(i) 和 f(i-1)，显然有 f(i)=max(f(i-1)+nums[i],nums[i])：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> v(n);
        int Max_sum=nums[0];
        v[0]=nums[0];
        for(int i=1;i<n;i++){
            v[i]=max(v[i-1]+nums[i],nums[i]);
            Max_sum=max(Max_sum,v[i]);
        }
        return Max_sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Leetcode152.乘积最大子数组

Leetcode152.乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2*10⁴
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32位 整数

本题如果继续使用 f(i)=max(f(i-1)+nums[i],nums[i]) 动态规划，会出现问题，如下示例：

nums = [3,5,-2,6,-3]

如果按照 Leetcode53 中递推方法，则 f=[3,15,-2,6,-3]，但显然最大乘积是 540，与求解答案不符。原因在于 本问题不具有最优子结构性质，即 f(i) 并不能由 f(i-1) 得到。因为负号的原因，f(2) 选取最大子数组乘积的时候 f(2) 只取自己，而 f(3) 也并没有取 f(2)，因此在 f(4) 时也没法兼顾到前面的负数。

因为是负数的原因，原本想通过记录上一次 nums 为负数的位置 pre ，遇到 nums[i]<0 时 f(i) 取 [nums[pre], nums[i]] 部分，若 f(nums[pre-1])>0 则乘上该值。并且 遇到 nums[i]==0 时需要将 pre 置 -1，表示前面无有效负数。几经修改还是失败了……

参考 力扣官方题解，既然是负号造成的问题，不妨同时维护最大值 f_max(i) 和最小值 f_min(i)，那么一定有：

fmax(i)=max(fmax(i-1)*nums[i],fmin(i-1)*nums[i],nums[i])
fmin(i)=min(fmax(i-1)*nums[i],fmin(i-1)*nums[i],nums[i])
1
2

以 nums = [3,5,-2,6,-3,-7] 为例：

• fmax(0)=3, fmin(0)=3
• fmax(1)=max(fmax(0)*nums[1],fmin(0)*nums[1],nums[1])=15,
  fmin(1)=min(fmax(0)*nums[1],fmin(0)*nums[1],nums[1])=5,
• fmax(2)=max(fmax(1)*nums[2],fmin(1)*nums[2],nums[2])=-2,
  fmin(2)=min(fmax(1)*nums[2],fmin(1)*nums[2],nums[2])=-30,
• fmax(3)=max(fmax(2)*nums[3],fmin(2)*nums[3],nums[3])=6,
  fmin(3)=min(fmax(2)*nums[3],fmin(2)*nums[3],nums[3])=-180,
• fmax(4)=max(fmax(3)*nums[4],fmin(3)*nums[4],nums[4])=540,
  fmin(4)=min(fmax(3)*nums[4],fmin(3)*nums[4],nums[4])=-18,
• fmax(5)=max(fmax(4)*nums[5],fmin(4)*nums[5],nums[5])=126,
  fmin(5)=min(fmax(4)*nums[5],fmin(4)*nums[5],nums[5])=-3780,

因此最大子数组乘积为540。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> v_max(n);
        vector<int> v_min(n);
        v_max[0]=nums[0];
        v_min[0]=nums[0];
        int Max_mul=nums[0];
        
        for(int i=1;i<n;i++){
            v_max[i]=max(max(v_max[i-1]*nums[i],v_min[i-1]*nums[i]),nums[i]);
            v_min[i]=min(min(v_max[i-1]*nums[i],v_min[i-1]*nums[i]),nums[i]);
            Max_mul=max(Max_mul,v_max[i]);
        }
        return Max_mul;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Leetcode337.打家劫舍 III

Leetcode337.打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
树的节点数在 [1, 10⁴] 范围内
0 <= Node.val <= 10⁴

从最小子问题入手，一个节点的树的最高金额显然是自己，两个节点的树的最高金额显然是较大的节点。对于三个节点的满二叉树，如果选择了根节点，就不能选择左右子节点；如果不选根节点，就可以选择左右子节点。显然一个状态表不足以记录信息，需要使用两个状态表分别记录是否包含根节点的最高金额：f[i] 表示包含根节点的最高金额，g[i] 表示不包含根节点的最高金额。

由于本题的数据结构是树而非数组，因此需要使用特殊的数据结构记录节点到 f 和 g 的映射，即 map 数据结构。

class Solution {
public:
    map<TreeNode*,int> f,g; // f为包含root的最高金额，g为不包含root的最高金额
    void dfs(TreeNode* root){
        if(root==nullptr)   return;
        dfs(root->left);
        dfs(root->right);
        f[root]=root->val+g[root->left]+g[root->right];
        g[root]=max(f[root->left],g[root->left])+max(f[root->right],g[root->right]);
        return;
    }
    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root],g[root]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Leetcode91.解码方法

Leetcode91.解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回解码方法的总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = “12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2：
输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3：
输入：s = “06”
输出：0
解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）。
提示：
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

按照动态规划的基本思路，将原问题分解，考虑字符串中一个元素的最优解。设 f(i) 表示 s[0…i] 的解码总数，显而易见有 f(0) = s[0]==0 ? 0 : 1。下面考虑 f(i) 和 f(i-1) 的关系，设函数 decode(c1,c2) 表示 c1 和 c2 组成的两位数字是否能够映射回字母：

if(s[i]=='0'){					//s[i]为0，则只能s[i-1]和s[i]合并
	f[i]=f[i-2]*decode(s[i-1],s[i]);	//如果合并成功，解码总数与f[i-2]相同，否则无法解码
}else{							//s[i]不为0
	if(!decode(s[i-1],s[i])){	//s[i-1]和s[i]组成的两位数字不能映射回字母
		f[i]=f[i-1];					//s[i]单独一个数字，解码总数与f[i-1]相同
	}else{						//s[i-1]和s[i]组成的两位数字能映射回字母
		f[i]=f[i-1]+f[i-2];				//s[i]单独时为f[i-1]，与s[i-1]组合时为f[i-2]
	}
}
1
2
3
4
5
6
7
8
9

下面确定初值情况：

f[0] = s[0]=='0' ? 0 : 1;
if(s[1]=='0'){
	f[1]=decode(s[0],s[1]);
}else{		//s[1]不是0，则可以是{s[0],s[1]}或者s[0...1]
	f[1]=f[0]+decode(s[0],s[1]);
}
1
2
3
4
5
6

其中函数 decode(c1,c2) 根据题意不难写出。

class Solution {
public:
    bool decode(char c1,char c2){
        if(c1=='0') return false;
        else if(c1=='1')    return true;
        else if(c1=='2'){
            if(c2>='0'&&c2<='6')    return true;
            else                    return false;
        }else       return false;
    }
    int numDecodings(string s) {
        int n=s.length();
        vector<int> f(n);

        f[0] = s[0]=='0' ? 0 : 1;
        if(n==1)    return f[0];
        else if(s[1]=='0'){
            f[1]=decode(s[0],s[1]);
        }else{
            f[1]=f[0]+decode(s[0],s[1]);
        }
        
        for(int i=2;i<n;i++){
            if(s[i]=='0'){
                f[i]=f[i-2]*decode(s[i-1],s[i]);
            }else{
                if(!decode(s[i-1],s[i])){
                    f[i]=f[i-1];
                }else{
                    f[i]=f[i-1]+f[i-2];
                }
            }
        }
        
        return f[n-1];
    }
};
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

Leetcode97.交错字符串

Leetcode97.交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true
示例 2：
输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
输出：false
示例 3：
输入：s1 = “”, s2 = “”, s3 = “”
输出：true
提示：
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

这个问题显然有个前提，如果 |s1|+|s2|≠|s3| 则不可能拼接成功。考虑状态数组，一维状态数组显然解决不了问题，那么 考虑二维数组。一开始使用状态数组 dp[i][j] 表示 s1[0…i] 和 s2[0…j] 能否拼接成 s3[0…(i+j+1)] ，但递推需要更多的初值无法获得。后来发现拼接时完全可以只用 s1 或 s2，也就是说 s1 和 s2 的长度需要从 0 开始计数，因此 i 和 j 应该表示长度而非下标，使用状态数组 dp[i][j] 表示 s1[0…i-1] 和 s2[0…j-1] 能否拼接成 s3[0…(i+j-1)]。

于是初值也很好确定：

dp[0][0]=true;
dp[0][j]=s2[0...j-1]==s3[0...j-1];
dp[i][0]=s1[0...i-1]==s3[0...i-1];
1
2
3

不过这样的赋值方法需要 O(max(i,j)) 的时间复杂度，因为重复比较了前 i-1 或 j-1 位字符，相当耗时。可以采用递推：

dp[0][0]=true;
dp[0][j]=dp[0][j-1] && s2[j-1]==s3[j-1];
dp[i][0]=dp[i-1][0] && s1[i-1]==s3[i-1];
1
2
3

下面考虑状态转移方程，如果 s1[0…i-1] 和 s2[0…j-1] 拼接成 s3[0…(i+j-1)]，那么 s3[0…(i+j-1)] 必然来自 s1[i-1] 或 s2[j-1]：如果来自 s1[i-1]，那么只需要看 dp[i-1][j]；如果来自 s2[j-1]，那么只需要看 dp[i][j-1]。因此有状态转移方程如下：

dp[i][j] = dp[i-1][j]&&s1[i-1]==s3[i+j-1] || dp[i][j-1]&&s2[j-1]==s3[i+j-1];
1

遂AC：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.length();
        int n=s2.length();
        if(m+n!=s3.length())    return false;

        vector<vector<bool> > dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=1;i<=m;i++){
            dp[i][0]=dp[i-1][0] && s1[i-1]==s3[i-1];
        }
        for(int j=1;j<=n;j++){
            dp[0][j]=dp[0][j-1] && s2[j-1]==s3[j-1];
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = dp[i-1][j]&&s1[i-1]==s3[i+j-1] || dp[i][j-1]&&s2[j-1]==s3[i+j-1];
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23