大家好,我是开车的阿Q,自动驾驶的时代已经到来,没时间解释了,快和阿Q一起上车。作为自动驾驶系统工程师,必须要有最好的C++基础,让我们来一起刷题吧。
题目考察的知识点
动态规划
题目解答方法的文字分析
这道题目要求在最多进行k次买卖的情况下计算农场主人能获得的最大利润。每次买卖包括一次买入和一次卖出,而且在买入新的牛之前必须已经卖掉手头上的牛。
为了解决这个问题,我们可以使用动态规划来计算最大利润。我们需要定义一个二维数组 dp[i][j]
,表示在第 i 天进行了 j 次买卖后的最大利润。然后,我们遍历数组中的每个价格,并根据动态规划的状态转移方程来更新利润。
具体解答步骤如下:
- 初始化二维数组
dp
,大小为k + 1
行,prices.size()
列。其中,dp[i][j]
表示在第 i 天进行了 j 次买卖后的最大利润,初始值为0。 - 对于第一行
dp[0][j]
,表示在第 0 天(即还未开始买卖)进行了 j 次买卖后的最大利润,初始值为0。 - 对于第一列
dp[i][0]
,表示在任意一天进行了 0 次买卖后的最大利润,初始值为0。 - 遍历数组中的每个价格
prices[i]
,对于每个价格,我们需要更新dp[i][j]
的值。具体更新方式如下:不进行买卖:dp[i][j] = dp[i-1][j],即当天不进行买卖,利润与前一天的利润相同。进行买卖:dp[i][j] = max(dp[i][j], dp[i-1][j-1] + prices[i] - prices[i-1]),即当天进行买卖,利润为前一天进行 j-1 次买卖后的利润,加上今天的价格与昨天的价格之差。 - 最终的结果为
dp[prices.size()-1][k]
,表示在最后一天进行了 k 次买卖后的最大利润。
本题解析所用的编程语言
C++
完整且正确的编程代码
#include <vector> #include <algorithm> using namespace std; class Solution { public: int maxProfitII(vector<int>& prices, int k) { int n = prices.size(); if (k == 0 || n < 2) { return 0; } // 如果 k 大于等于数组长度的一半,相当于可以进行无限次买卖 // 这种情况下可以转化为不限制次数的买卖问题,直接返回最大利润即可 if (k >= n / 2) { int maxProfit = 0; for (int i = 1; i < n; ++i) { if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; } vector<vector<int>> dp(k + 1, vector<int>(n, 0)); for (int i = 1; i <= k; ++i) { int maxDiff = -prices[0]; // 保存第 i 次买入后的最大利润 for (int j = 1; j < n; ++j) { dp[i][j] = max(dp[i][j - 1], prices[j] + maxDiff); maxDiff = max(maxDiff, dp[i - 1][j] - prices[j]); } } return dp[k][n - 1]; } };