DP章节

DP模板

  1. 确定数组dp[i]的含义，以及下标i的含义
  2. 确定数组dp[i]的递推公式
  3. 确定数组dp[i]的初始值
  4. 确定遍历顺序
  5. 举例推导

基础DP

斐波那契数列

递归

容易想到递归的方法来实现

1
2
3
4
5
6
7
8
class Solution {
public:
    int fib(int n) {
        if(n<=1)
            return n;
        return fib(n-1) + fib(n-2);
    }
};

时间复杂度为O(n!)，空间复杂度为O(n)

DP

DP数组的含义是i位置的斐波那契数列值是dp[i]

递推公式为dp[i] = dp[i-1]+dp[i-2]

DP数组初始值dp[0]=0,dp[1]=1

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

时间复杂度为O(n)，空间复杂度为O(n)

DP优化

因为dp[i]的值只与其前两个值，即dp[i-1]和dp[i-2]有关，则可以不需要借助容器vector来记录，而是只用三个变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int n) {
        if(n == 0)  return 0;
        int v0 = 0, v1 = 1;
        int sum = 1;
        for(int i = 2; i <= n; i++)
        {
            sum = v0 + v1;
            v0 = v1;
            v1 = sum;
        }
        return v1;
    }
};

时间复杂度为O(n)，空间复杂度为O(1)

总结

由于 F(n) 只和 F(n-1)与 F(n-2)有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)，即只需要借助三个变量来完成

爬楼梯

该题允许向上攀爬一个或两个台阶，返回n级台阶总共有多少种不同的攀爬方法

DP思路

1
2
3
4
当n为1时，有1种方式
当n为2时，有2种方式
当n为3时，有3种方式
当n为4时，有5种方式

可以看出，当阶数为n时，是n-1和n-2级阶数方法的总和

  • 确定DP数组含义

    DP[i]表示在台阶i时的攀爬方法

  • 确定递推公式

    DP[i] = DP[i - 1] + DP[i - 2];

  • 确定初始值

    DP[1] = 1, DP[2] = 2

  • 确定遍历顺序

    遍历顺序为正序，从头到尾遍历数组

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 3)  return n;
        int res = 0;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

DP优化

与[上一题](# DP优化)优化方式类似，因为dp[i]的值只与其前两个值，即dp[i-1]和dp[i-2]有关，因此可以使用滚动数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 3)  return n;
        int res = 0;
        int q = 1, w = 2, e = 3;
        for(int i = 3; i <= n; i++)
        {
            e = q + w;
            q = w;
            w = e;
        }
        return e;
    }
};

总结

由于 F(n) 只和 F(n-1)与 F(n-2)有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)，即只需要借助三个变量来完成

使用最小花费爬楼梯

该题给出爬每层楼梯的花费，允许每次爬一个或两个阶梯，要求使用最低花费爬到楼梯顶部

DP思路

可以看出，当爬到第n层楼梯时，当前总共的花费与n-1级楼梯的花费有关，也就是说当前状态可以由之前的状态推导出来

  • 确定DP数组含义

    DP[i]表示在台阶i时的总共花费

  • 确定递推公式

    DP[i] = min(DP[i - 1] + costs[i - 1], DP[i- 2] + costs[i - 2];

  • 确定初始值

    DP[1] = 0, DP[2] = 0，初始值应由递推公式中的cost[i]来决定

  • 确定遍历顺序

    遍历顺序为正序，从头到尾遍历数组

DP

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

DP优化

类似的，因为dp[i]的值只与其前两个值，即dp[i-1]和dp[i-2]有关，因此可以使用滚动数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int q = 0, w = 0, e = 0;
        for(int i = 2; i <= cost.size(); i++)
        {
            e = min(q + cost[i-2], w + cost[i-1]);
            q = w;
            w = e;
        }
        return e;
    }
};

总结

由于 F(n) 只和 F(n-1)与 F(n-2)有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)，即只需要借助三个变量来完成

不同路径

该题有一个m*n大小的网格图，要求只能一次向下或者向右移动一步，返回总共不同的路径数

DP思路

若为1*1的网格，则有1条路径

2*2的网格，有2条路径

3*2或者是2*3的网格，则有3条路径

3*3的网格中，有6条路径

由上可知，在m*n的网格当中，其路径总数等于 (m-1)*n网格的路径总数加上m*(n-1)网格的路径总数，因此将使用DP算法

  • 确定数组DP[i][j]含义

    DP[i][j]表示的是在i*j的网格当中，总共有DP[i][j]条路径

  • 确定初始值

    为了方便，数组DP[i][j]表示第i行第j列，且不影响结果

    DP[1][j]均为1，即第一行中的数，代表着1*n的所有网格

    DP[i][1]均为1，同理

  • 确定状态转移方程

    DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

  • 确定遍历顺序

    从i=2开始遍历到n，正向遍历

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
pubulic:
	int uniquePaths(int m, int n)
	{
		if(m == 1 || n == 1)
			return 1;
		vector<int> row(n + 1,1);
		vector<vector<int>> dp(n + 1,row);
		//dp数组全部元素初始化为1
		for(int i = 2; i <= m; i++)
			for(int j = 2; j <= n; j++)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		return dp[m][n];
	}
};

时间复杂度为O(n^2)，遍历网格中的所有元素，空间复杂度为O(n^2)，为网格中的每个元素独立创建一份空间

DP优化

由上可知，当遍历时，当前位置下的元素只与同行上一列元素和同列上一行元素有关，因此可以只使用一维数组来进行空间的优化

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

总结

初始化中只需要对首行和首列元素进行初始化为1的操作

不同路径 II

与I比较，该题多了障碍的设置，要求所有需要经过障碍所在位置的路径都不能被通过

DP思路

如果在dp[i-1][j]位置上有障碍，那么需要通过该点通往任意位置都将无法通过，这样可以通过将dp[i-1][j]=0，而dp[i][j] = dp[i-1][j] + dp[i][j-1] = dp[i][j-1]

  • 确定数组DP[i][j]含义

    DP[i][j]表示的是在i*j的网格当中，排除有障碍的，总共有DP[i][j]条路径

  • 确定初始值

    该题中 数组DP[i+1][j+1]表示第i行第j列，并且只需要对首列和首行的元素进行初始化

    数组所有元素初始化为0，遍历数组中第0行和第0列的元素，如果当前位置上的元素没有遇到障碍，则将当前元素初值设为1，同时，如果遇到有障碍，那么在障碍之后的所有元素值都应该初始化为0

    如数组[[0,0],[1,1],[0,0]]，这时，对应的dp数组最终应该被初始化为[[1,1],[0,0],[0,0]]

  • 确定状态转移方程

    DP[i][j] = DP[i - 1][j] + DP[i][j - 1]，与上题一致

  • 确定遍历顺序

    正向遍历，与上题遍历顺序一致，但该题因为下标代表的含义不同，所以应该从i=1开始遍历到n-1

DP

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)   return 0;
        vector<int> row(n,0);
        vector<vector<int>> dp(m, row);

        for(int i = 0; i < m; i++)
        {
            if(obstacleGrid[i][0]==0)
                dp[i][0] = 1;
            else
                break;
        }
        for(int j = 0; j < n; j++)
        {
            if(obstacleGrid[0][j]==0)
                dp[0][j] = 1;
            else
                break;
        }
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
            {
                if(obstacleGrid[i][j]==1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        return dp[m-1][n-1];
    }
};

DP优化

同样地，该题也可以只使用一个一维滚动数组来减小空间开销

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)   return 0;
        vector<int> dp(n,0);
        bool flag = false;
        
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(j==0 && flag)
                    continue;
                if(obstacleGrid[i][j]==1)
                {
                    dp[j] = 0;
                    if(j==0)
                        flag = true;
                }
                else if(j==0)
                    dp[j] = 1;
                else
                    dp[j] += dp[j-1];
            }
        return dp[n-1];
    }
};

因为不能另外用一个循环来进行首列的初始化，因此借助flag变量来标记是否遇到障碍，如果遇到，之后的元素都将初始化为0；而首行元素则不需要，因为所有元素都被初始化为0，并且当前元素的值，即dp[i]只与自身大小与左边元素大小有关，如[[0,0,0,1,0,0]]数组中，在遇到障碍之前的dp数组为[1,1,1]，遇到障碍则dp[3]=0，之后的元素dp[i] += dp[i-1]均为0

总结

与上一题对比，该题处理方法的不同主要在于 初始化中不能将首行和首列所有元素都初始化为1，因为可能会在首行或首列元素中放置了障碍，并且，遇到障碍之后的首行或首列元素都应该初始化为0，意味着在首行或首列遇到障碍之后的元素都将没有路径能够到达。

不同的二叉搜索树

该题中给定一个整数，需要由1-n不同结点值组成一颗二叉搜索树，返回最多能组成互不相同的种树

DP思路

当n为1，只有1种二叉搜索树

当n为2，有2种二叉搜索树

当n为3，有5种二叉搜索树。 再细分，当以1为根结点，有两个大于1的数在根结点右边，则此时右子树可以组成n为2情况下的2种二叉搜索树；当以2为结点，同理有1个小于2的数在左子树，有1个数在右子树；当以3为结点，有2个数在左子树。

综上，可得n=3时，二叉搜索树数量=(右子树n=2的数量 * 左子树n=0的数量) + (右子树n=1的数量 * 左子树n=1的数量) + (右子树n=0的数量 * 左子树n=2的数量)

  • 确定数组dp[i]含义

    dp[i]表示的是i个结点下能组成二叉搜索树的数量

  • 确定初始值

    dp[0]=1，空结点时能组成1种二叉搜索树

    dp[1]=1

    dp[2]=2

  • 确定状态转移方程

    dp[i]=dp[j-1]*dp[i-j]，需要嵌套一层循环

  • 确定遍历顺序

    正向遍历，从i=3开始遍历到n，从j = 1遍历到 j = i

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numTrees(int n) {
        if(n==1)    return 1;
        if(n==2)    return 2;

        vector<int> dp(n+1,0);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++)
            for(int j = 1; j <= i;j++)
                dp[i] += dp[j - 1] * dp[i-j];
        return dp[n];
    }
};

数学解法

卡特兰数

1
2
3
4
5
6
7
8
9
10
11
12
//公式：C0 = 1 , Cn+1 = 2(2n+1)/(n+2)*Cn 

class Solution {
public:
    int numTrees(int n) {
        long long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;
    }
};

总结

该题难以推出状态转移方程，不妨细分情况，尽可能将之前的状态套进当前状态来考虑

整数拆分

该题给定一个正整数n，将其拆分为n个正整数的和，并返回这些和的最大化乘积

DP思路

算出前8个正整数的最大乘积为

1
2
1	2	3	4	5	6	7	8
1	1	2	4	6	9	12	18

将8拆分成以下的情况，

8 = j + (i - j)，此时，j和i - j不再拆分，那么 n=8的最大乘积 = i * (i - j)；若继续拆分i - j，那么 n=8的最大乘积 = i * (n = (i - j)的最大乘积)

综上，可以得到 dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))

  • 确定数组dp[i]含义

    dp[i]表示的是整数i拆分的正整数的最大乘积

  • 确定初始值

    dp[1]=1

    dp[2]=1

    dp[3]=2

  • 确定状态转移方程

    dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))，需要嵌套一层循环

  • 确定遍历顺序

    正向遍历，从i=4开始遍历到n，从j = 1遍历到j = i

DP

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
            for(int j = 1; j <= i/2; j++)
                dp[i] = max(dp[i], max(j*(i-j), dp[i-j]*j));
        return dp[n];
    }
};

贪心

数学证明：

$$ {函数极值证明法}
函数极值证明法

显然，如果将给定的正整数拆分成尽可能多的某个特定的正整数，则这些正整数的乘积最大。

定义函数 f(x)f(x) 表示将给定的正整数 nn 拆分成尽可能多的正数 xx 的情况下的最大乘积，则可以将 nn 分成 \dfrac{n}{x}
x
n
​
项，此时 f(x)=x^{\frac{n}{x}}f(x)=x
x
n
​

，目标是求 f(x)f(x) 的最大值，即

\mathop{\max}\limits_{x}(f(x))
x
max
​
(f(x))

可以将 f(x)f(x) 写成如下形式：

f(x)=x^{\frac{n}{x}}=e^{\frac{n \ln x}{x}}
f(x)=x
x
n
​

=e
x
nlnx
​

令 g(t)=e^tg(t)=e
t
，h(x)=\dfrac{\ln x}{x}h(x)=
x
lnx
​
，则有 f(x)=g(n \cdot h(x))f(x)=g(n⋅h(x))。由于 g(t)g(t) 是单调递增的，n>0n>0，因此 h(x)h(x) 与 f(x)f(x) 的单调性相同。

计算 h(x)h(x) 的驻点，即 h’(x)=\dfrac{1- \ln x}{x^2}=0h
′
(x)=
x
2

1−lnx
​
=0 的点，得到驻点为 x=ex=e。

由于当 0<x<e0<x<e 时 h’(x)>0h
′
(x)>0，当 x>ex>e 时 h’(x)<0h
′
(x)<0，因此 x=ex=e 是 h(x)h(x) 的极大值点，也是 f(x)f(x) 的极大值点。由于函数 f(x)f(x) 的定义域连续，因此极大值点唯一，也是最大值点。

因此，当 x=ex=e 时，f(x)f(x) 取到最大值，\max f(x)=f(e)=e^{\frac{n}{e}}maxf(x)=f(e)=e
e
n
​

。

由于 ee 不是整数，因此使用与 ee 最接近的整数作为 xx 的值，xx 可以是 22 或 33，此时需要比较 f(2)f(2) 与 f(3)f(3) 的大小，可以通过计算 \dfrac{f(3)}{f(2)}
f(2)
f(3)
​
进行比较。

\dfrac{f(3)}{f(2)}=\dfrac{e^{n \cdot h(3)}}{e^{n \cdot h(2)}}=e^{n \cdot h(3)-n \cdot h(2)}=e^{n \cdot (\frac{\ln 3}{3} - \frac{\ln 2}{2})}=e^{\frac{n}{6} \cdot (2 \ln 3 - 3 \ln 2)}=e^{\frac{n}{6} \cdot (\ln 9 - \ln 8)}
f(2)
f(3)
​

e
n⋅h(2)

e
n⋅h(3)

​
=e
n⋅h(3)−n⋅h(2)
=e
n⋅(
3
ln3
​
−
2
ln2
​
)
=e
6
n
​
⋅(2ln3−3ln2)
=e
6
n
​
⋅(ln9−ln8)

由于 \ln 9 > \ln 8ln9>ln8，因此 \dfrac{f(3)}{f(2)}>1
f(2)
f(3)
​

1，即 f(3)>f(2)f(3)>f(2)。当 x=3x=3 时，可以得到最大乘积。因此，应该将给定的正整数拆分成尽可能多的 33。

根据 nn 除以 33 的余数进行分类讨论：

如果余数为 00，即 n=3m(m \ge 2)n=3m(m≥2)，则将 nn 拆分成 mm 个 33；

如果余数为 11，即 n=3m+1(m \ge 1)n=3m+1(m≥1)，由于 2 \times 2 > 3 \times 12×2>3×1，因此将 nn 拆分成 m-1m−1 个 33 和 22 个 22；

如果余数为 22，即 n=3m+2(m \ge 1)n=3m+2(m≥1)，则将 nn 拆分成 mm 个 33 和 11 个 22。

上述拆分的适用条件是 n \ge 4n≥4。如果 n \le 3n≤3，则上述拆分不适用，需要单独处理。

如果 n=2n=2，则唯一的拆分方案是 2=1+12=1+1，最大乘积是 1 \times 1=11×1=1；

如果 n=3n=3，则拆分方案有 3=1+2=1+1+13=1+2=1+1+1，最大乘积对应方案 3=1+23=1+2，最大乘积是 1 \times 2=21×2=2。

这两种情形可以合并为：当 n \le 3n≤3 时，最大乘积是 n-1n−1。
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int)pow(3, quotient);
        } else if (remainder == 1) {
            return (int)pow(3, quotient - 1) * 4;
        } else {
            return (int)pow(3, quotient) * 2;
        }
    }
};

总结

DP思路考虑状态转移方程时，把正整数n拆分成 j和n-j来考虑，自然得到拆分的一种乘积为j * (n - j)，考虑到上一个的状态，拆分为n - j还可以继续拆分，此时，另一种乘积则为j * dp[n - j]

贪心思路需要用到复杂数学证明的结论——尽可能将数拆分成2或3时的乘积最大。

If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you’d only use it for n=2 and n=3, where it’s needed).

For the rest I agree, 33 is simply better than 22*2, so you’d never use 2 more than twice.、

股票系列(状态机DP)

买卖股票的最佳时机

单笔交易的最大利润

DP

用二维数组dp储存持有股票和非持有股票两种状态下的最大利润，

  • 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])，即继续保持前一天持股或持当天股的最大值，也就是保持最低买入股价

  • 根据状态转移方程将dp[0][0] = 0, dp[0][1] = -price[0]作为初始值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 0, dp[0][1] = -prices[0];
        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];
    }
};

优化DP

两种状态更新过程中，只需要dp[i - 1][0]和dp[i - 1][1]两个值，那么即可用两个变量代替二维数组

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

买卖股票的最佳时机 II

多笔交易的最大利润

DP

用二维数组dp储存持有股票和非持有股票两种状态下的最大利润

  • 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], dp[i - 1][0] - prices[i])，即继续保持前一天持股，或者将前一天持的股卖出获得利润，同一天入股的最大利润

  • 根据状态转移方程将dp[0][0] = 0, dp[0][1] = -price[0]作为初始值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 0, dp[0][1] = -prices[0];
        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];
    }
};

优化DP

同样地，在更新过程中只用到了dp[i - 1][0]和dp[i - 1][1]两个值，用两个变量代替二维数组，另外还需要一个变量保存中间值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        f0 = 0, f1 = -prices[0], tmp = 0;
        for(const auto & price : prices)
        {
        	tmp = f0;
        	f0 = max(f0, f1 + price);
        	f1 = max(f1, tmp - price);
        }
        return f0;
    }
};

贪心解法

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

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

卖出股票后不能在第二天买入股票

DP

用二维数组dp储存持有股票和非持有股票两种状态下的最大利润

  • 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], dp[i - 2][0] - prices[i])，即继续保持前一天持股，或者将两天前持的股卖出获得利润，然后在当天入股的最大利润

  • 根据状态转移方程将dp[0][0] = 0, dp[0][1] = -price[0]作为初始值

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

在考虑一个长度为3的数组作输入时，如[2, 1, 4]，初始值被设为第一天的利润，当i=1时并没有更新，显然不合理，对此，可以将else 语句改为dp[i][1] = max(dp[i - 1][1], prices[i])；另外，也可以不增加额外的判断语句，将二维数组长度更改为dp[n + 1][2]或者dp[n + 2][2]

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
-----dp[n+1][2]-----
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][2];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 0; i < n; i++)
        {
            dp[i + 1][0] = max(dp[i][0], dp[i][1] + prices[i]);
            if(i - 1 >= 0)
                dp[i + 1][1] = max(dp[i][1], dp[i - 1][0] - prices[i]);
            else
                dp[i + 1][1] = dp[i][1];
        }
        return dp[n][0];
    }
};

-----dp[n+2][2]-----
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 2][2];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 0, dp[1][1] = -prices[0];
        for (int i = 0; i < n; i++)
        {
            dp[i + 2][0] = max(dp[i + 1][0], dp[i + 1][1] + prices[i]);
            dp[i + 2][1] = max(dp[i + 1][1], dp[i][0] - prices[i]);
        }
        return dp[n + 1][0];
    }
};

优化DP

可以观察到，更新二维数组时，只用到dp[i - 1][0],dp[i - 1][1]和dp[i - 2][0]三个值，即可以用三个变量代替二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int f0 = 0, f1 = -prices[0], last = 0, tmp = 0, second = 0;
        for (const auto& price : prices)
        {
            tmp = f0;
            f0 = max(f0, f1 + price);
            f1 = max(f1, second - price);
            second = last;
            last = f0;
        }
        return f0;
    }
};

买卖股票的最佳时机含手续费

无限制次数交易，但每笔交易需要手续费，是买卖股票的最佳时机II的变形题

DP

用二维数组dp储存持有股票和非持有股票两种状态下的最大利润

  • 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], dp[i - 1][0] - prices[i])，即继续保持前一天持股，或者将前一天持的股卖出获得利润，当天入股的最大利润

  • 根据状态转移方程将dp[0][0] = 0, dp[0][1] = -price[0]作为初始值

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

买卖股票的最佳时机 IV

最多完成k笔交易，需要增加一种状态表示交易数

DFS递归+记忆化

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
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        int memo[n+1][k+2][2];
        memset(memo, -1, sizeof memo);

        function<int (int, int, bool)> dfs = [&](int i, int j, bool flag)-> int{
            if(j < 0) // 交易次数为负，返回INT_MIN
                return INT_MIN;
            if(i < 0) // 初始化时并没有利润，返回INT_MIN或0
                return flag ? INT_MIN : 0;
            if(memo[i][j][flag] != -1)
                return memo[i][j][flag];
            if(flag) // 持有股票
            {
                memo[i][j][flag] = max(dfs(i - 1, j, 1), dfs(i - 1, j, 0) - prices[i]);
                return memo[i][j][flag];
            }
            memo[i][j][flag] = max(dfs(i - 1, j, 0), dfs(i - 1, j - 1, 1) + prices[i]);
            return memo[i][j][flag];
        };

        return dfs(n - 1, k, 0);
    }
};

递归结束条件：交易次数不足 或 遍历完所有天数的股票，前者返回负无穷，后者返回0或负无穷作为从头开始搜索的初始条件——不持股票状态下，最大利润为0；持股票时，最大利润为负无穷

DP

用三维数组dp储存持股和交易次数两大类状态下的最大利润

  • dp[i][j][0]表示当前不持有股票，交易次数为j (j <= k)时的最大利润，可得dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i])，即继续保持前一天的最大利润，不持股也不交易，或者是在前一天持股，当天卖出状态下的最大利润

  • dp[i][j][1]表示当前**持有股票，交易次数为j (j <= k)**的最大利润，可得dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i])，即继续保持前一天持股不交易，或者**在前一天不持股，当天购入状态下的最大利润**。统一将卖出股票时才算交易完成，交易次数+1

  • 根据状态转移方程，三维数组元素初始化为大负数（由题目数据量可知<1000），再将dp[0][j][0] = 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(int k, vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][k + 2][2]; // [-1, k] 避免 k = -1 情况，整体右移； i同理
        memset(dp, -0x7f, sizeof dp);// 全都初始化为INT_MIN
        // fill_n(dp, (n+1)*2*(k+2), INT_MIN); 
        for(int j = 0; j < k + 2; j++) // 在交易次数为0且不持股时，最大利润初始化为0
        // {
            // dp[1][j][0] = 0;
            // dp[1][j][1] = -prices[0];
        // }
            dp[0][j][0] = 0;
        // dp[0][j][1]? ---> 需要 i 从 0 开始遍历
        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j < k + 2; j++)
            {
                dp[i + 1][j][0] = max(dp[i][j][0], dp[i][j - 1][1] + prices[i]);
                dp[i + 1][j][1] = max(dp[i][j][1], dp[i][j][0] - prices[i]);
            }
        }
        return dp[n][k + 1][0];
    }
};

由DFS翻译成递推，可得初始条件为dp[0][j][0] = 0, dp[0][j][1] = -prices[0]，可以从i=1开始遍历而不是i=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(int k, vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][k + 2][2]; // [-1, k] 避免 k = -1 情况，整体右移； i同理
        memset(dp, -0x7f, sizeof dp);// 全都初始化为INT_MIN
        // fill_n(dp, (n+1)*2*(k+2), INT_MIN); 
        for(int j = 0; j < k + 2; j++) // 在交易次数为0且不持股时，最大利润初始化为0
        {
            dp[0][j][0] = 0;
            dp[0][j][1] = -prices[0];
        }
            // dp[0][j][0] = 0;
        // dp[0][j][1]? ---> 需要 i 从 0 开始遍历
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j < k + 2; j++)
            {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i - 1]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i - 1]);
            }
        }
        return dp[n][k + 1][0];
    }
};

买卖股票的最佳时机 III

最多完成两笔交易，固定数组第三维为3，表示交易的次数

DP

用三维数组dp储存持股和交易次数两大类状态下的最大利润

  • dp[i][j][0]表示当前不持有股票，交易次数为j (j <= 2)时的最大利润，可得dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i])，即继续保持前一天的最大利润，不持股也不交易，或者是在前一天持股，当天卖出状态下的最大利润

  • dp[i][j][1]表示当前**持有股票，交易次数为j (j <= 2)**的最大利润，可得dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i])，即继续保持前一天持股不交易，或者**在前一天不持股，当天购入状态下的最大利润**。统一将卖出股票时才算交易完成，交易次数+1

  • 根据状态转移方程，三维数组元素初始化为大负数（由题目数据量可知<100000），再将dp[0][j][0] = 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();
        int dp[n + 1][4][2]; // [-1, k] 避免 k = -1 情况，整体右移； i同理
        memset(dp, -0x7f, sizeof dp);// 全都初始化为INT_MIN
        // fill_n(dp, (n+1)*2*(k+2), INT_MIN); 
        for(int j = 0; j < 4; j++) // 在交易次数为0且不持股时，最大利润初始化为0
        // {
            // dp[1][j][0] = 0;
            // dp[1][j][1] = -prices[0];
        // }
            dp[0][j][0] = 0;
        // dp[0][j][1]? ---> 需要 i 从 0 开始遍历
        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j < 4; j++)
            {
                dp[i + 1][j][0] = max(dp[i][j][0], dp[i][j - 1][1] + prices[i]);
                dp[i + 1][j][1] = max(dp[i][j][1], dp[i][j][0] - prices[i]);
            }
        }
        return dp[n][3][0];
    }
};
DP章节
https://kevin346-sc.github.io/2022/12/02/DP章节/
作者
Kevin Huang
发布于
2022年12月2日
许可协议