作者:来知晓
公众号:来知晓
刷题交流QQ群:444172041

Git项目地址LeetCodeUsingC刷题笔记

本篇解法思路参考了labuladong的算法小抄里的文章《一个方法团灭 LeetCode 股票买卖问题》,将原来C++代码,根据C代码实现做了部分调整和简化。总体来看,东哥文章里面思路讲的已经很清楚了,下面总结下C代码实现对应框架时,个人认为的一些核心要点和注意事项。

核心框架


关键点

  • 理解状态遍历的思路本质,类似于知道初始条件,不断迭代所有可能,最终得到结果
  • 记住状态转移方程写法和初始条件,并灵活应用
  • 买前必须卖完
  • 买完再卖出去后才算一笔交易

若假设一共有n天股价数据,最大交易次数限制为K次,则0 <= i < n0 <= k <= K,可以推出:

状态转移方程:

dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + price[i]);
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]);

解释:

  • 简化问题,每天都只有两个状态,持有和不持有,当前状态跟前一个状态有关系,于是就可以从初始条件不断迭代,直到最后一天。
  • 另外,之所以每个是用max取结果,是因为dp存的一直是到今天截止当前状态对应的最大利润。所以我们的输出才可以是dp[n - 1][K][0]。

初始条件Base Case:

dp[-1][k][0] = 0;			// 注意此处的k表示0到k的操作次数所有值 
dp[-1][k][1] = -Infinity; 	// 表示不可能
dp[i][0][0] = 0;			// 注意此处的i表示0到i-1的天数所有值
dp[i][0][1] = -Infinity;

输出的最大利润:

dp[n - 1][k][0]  			// 最后一天,手上不持有股票的时候有最大利润

以上为核心框架分析,下面开始实战。

5道题中的易错点


买卖股票的最佳时机

K = 1,即仅允许交易一次的情况,因为我们最终只关心dp[n - 1][K][0]时的输出,所以状态转移方程中k可以直接取1,而dp[i - 1][0][0]恒为0,所以可以用k = 1一直递推,从而降维得到:

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i])

买卖股票的最佳时机 II

K = +infinity,即不限交易次数的情况,每天的dp里显然只需要存储最大交易次数对应的利润即可。而我们只关心最终dp[n - 1][K][0]的输出,且K无穷大时,dp[i - 1][K - 1][0] = dp[i - 1][K][0],所以状态转移方程可以化简为:

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])

买卖股票的最佳时机 III

K = 2,即仅能交易两次,注意以下两点:

  • 不能只用两个变量来表达,要用两个大小为3的一维数组,表示k从0一直取到2
  • 要注意数组初始值,不持有状态初始值全为0,持有状态初始全为负无穷大

最佳买卖股票时机含冷冻期(中等)

容易想到,冷冻期一天的限制条件可转化为:一旦发现卖出,则在下一天循环时跳过。以下为对应代码实现:

#include <limits.h>

// 采用状态机来遍历所有可能的状态
#define max(a, b) (a) > (b) ? (a) : (b)
int maxProfit(int* prices, int pricesSize)
{
   
    // k = +infinity
    int dp_i_0 = 0;
    int dp_i_1 = INT_MIN;
    int freeze_flag = 0;
    int i;
    for (i = 0; i < pricesSize; i++) {
   
        // dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + price[i]); // 不动或卖出
        // dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]); // 不动或买入
        if (freeze_flag == 1) {
   
            freeze_flag = 0;
            continue; // 卖出后冻结一天
        }
        int tmp_dp_i_0 = dp_i_0;
        // dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
        if (dp_i_1 + prices[i] > dp_i_0) {
    // 若卖出
            dp_i_0 = dp_i_1 + prices[i];
            freeze_flag = 1;
        }
        dp_i_1 = max(dp_i_1, tmp_dp_i_0 - prices[i]);

    }
    return dp_i_0;
}

但是以上代码在过用例{1,2,4}时,输出错误。分析发现,状态转移方程更新的不对,状态转移方程中这句:
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i])
应该是dp[i - 2][k - 1][0]。修改上面19-25行代码为:

int tmp_dp_i_0 = dp_i_0;
// dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
if (dp_i_1 + prices[i] > dp_i_0) {
    // 若卖出
    dp_i_0 = dp_i_1 + prices[i];
    freeze_flag = 1;
}
dp_i_1 = max(dp_i_1, pre_dp_i_0 - prices[i]);
pre_dp_i_0 = tmp_dp_i_0;

再测试时,依然输出结果不对。深入分析后,发现前面说的转化思路不对,continue会导致无法迭代每一步转移矩阵,从而无法得到所有可能情况。

比如输入{1,2,4}时,在不持有的可能中,第二天就卖了,检测到卖了标志,第三天就冻结了。而实际最优的结果不是取的第二天就卖,而是取的第二天持有,然后第三天卖这样的操作,才能获得利润最大化。所以代码根据其中的一种卖出可能,就当做真的已经卖出跳过其他可能的遍历了。

正确做法如下:

  • 修改状态转移方程,买入时,从前两天不持有状态的数组转移过来,i-1 变为 i-2
  • 不要跳过,而是遍历所有天数的可能

正确代码如下:

#include <limits.h>
#define max(a, b) (a) > (b) ? (a) : (b)
int maxProfit(int* prices, int pricesSize)
{
   
    // k = +infinity
    int dp_i_0 = 0;
    int dp_i_1 = INT_MIN;
    int i;
    int pre_dp_i_0 = 0;
    for (i = 0; i < pricesSize; i++) {
   
        // dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + price[i]); // 不动或卖出
        // dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - price[i]); // 不动或买入
        int tmp = dp_i_0; // 更新前
        dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); // 当前更新后
        dp_i_1 = max(dp_i_1, pre_dp_i_0 - prices[i]);
        pre_dp_i_0 = tmp; // 下次循环用时,就变成了前两天的
    }
    return dp_i_0;
}

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

此题要注意初始条件会从INT_MIN再减个手续费,可能导致整数类型溢出。需要注意防止超过int最小值, 如 INT_MIN + 1 - 2 就溢出了。

解决的小技巧:

// 原来
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee);
// 改为
int tmp = ((long long)dp_i_1 + prices[i] - fee < INT_MIN) ? 
           INT_MIN : (dp_i_1 + prices[i] - fee);
dp_i_0 = max(dp_i_0, tmp);

完整代码如下:

// 采用状态机来遍历
/**** 模板 ********** 状态转移方程: dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + price[i]); dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]); Base Case: dp[-1][k][0] = 0; dp[-1][k][1] = -Infinity; //不可能 dp[i][0][0] = 0; dp[i][0][1] = -Infinity; output: dp[n - 1][k][0] ********************/
#include <limits.h>
#define max(a, b) (a) > (b) ? (a) : (b)
int maxProfit(int* prices, int pricesSize, int fee)
{
   
    // k = +infinity
    int dp_i_0 = 0;
    int dp_i_1 = INT_MIN;
    int i;
    for (i = 0; i < pricesSize; i++) {
   
        // dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + price[i] - fee); // 卖出时才扣手续费
        // dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]);
        int tmp_dp_i_0 = dp_i_0;
        // 注意防止超过int最小值, 如 INT_MIN + 1 - 2 就溢出了
        int tmp = ((long long)dp_i_1 + prices[i] - fee < INT_MIN) ? INT_MIN : (dp_i_1 + prices[i] - fee);
        dp_i_0 = max(dp_i_0, tmp);
        dp_i_1 = max(dp_i_1, tmp_dp_i_0 - prices[i]);
    }
    return max(dp_i_0, dp_i_1);
}

LeetCode相关题目


完整C代码实现,可去GitHub仓:LeetCodeUsingC刷题笔记查看。