普陀做网站,做房地产自己要花钱开网站,江苏网站建设哪家好,技能训练企业网站建设可行性分析动态规划
思路#xff1a; 状态定义 假设 buy[i][j] 是第 i 天进行第 j 笔交易#xff0c;手上还买入一支股票的最大利润#xff1b;sell[i][j] 是第 i 天进行第 j 笔交易的最大利润#xff1b;状态转移#xff1a; 第 i 天进行第 j 笔交易#xff0c;手上还买入一支股票…动态规划
思路 状态定义 假设 buy[i][j] 是第 i 天进行第 j 笔交易手上还买入一支股票的最大利润sell[i][j] 是第 i 天进行第 j 笔交易的最大利润状态转移 第 i 天进行第 j 笔交易手上还买入一支股票 第 i - 1 天即为此状态第 i 天未进行操作即 buy[i - 1][j]第 i - 1 天进行第 j 笔交易第 i 天买入即 sell[i - 1][j] - prices[i]则 buy[i][j] max(buy[i - 1][j], sell[i - 1][j] - prices[i])第 i 天进行第 j 笔交易 第 i - 1 天进行了第 j 笔交易第 i 天未进行操作即 sell[i - 1][j]第 i - 1 天进行了第 j - 1 笔交易并且手上还持有一支股票第 i 天进行卖出即 buy[i - 1][j - 1] prices[i]则 sell[i][j] max(sell[i - 1][j], buy[i - 1][j - 1] prices[i])初始状态 buy[0][0] -prices[0]sell[0][0] 0初始化第 0 天第 0 - k 笔交易值为 INT_MIN / 2 buy[0][i] INT_MIN / 2; sell[0][i] INT_MIN / 2; 最大交易次数为天数的一半即 k std::min(k, size / 2)第 0 笔交易的时候进行修正避免 j - 1 溢出 buy[i][0] std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]); 最大利润为最后一天完成交易的最大值 *std::max_element(sell[size - 1].begin(), sell[size - 1].end());
class Solution {
public:int maxProfit(int k, vectorint prices) {int size prices.size();if (0 size) {return 0;}k std::min(k, size / 2);std::vectorstd::vectorint buy(size, std::vectorint(k 1));std::vectorstd::vectorint sell(size, std::vectorint(k 1));buy[0][0] -prices[0];sell[0][0] 0;for (int i 1; i k; i) {buy[0][i] INT_MIN / 2;sell[0][i] INT_MIN / 2;}for (int i 1; i size; i) {buy[i][0] std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]);for (int j 1; j k; j) {buy[i][j] std::max(buy[i - 1][j], sell[i - 1][j] - prices[i]);sell[i][j] std::max(sell[i - 1][j], buy[i - 1][j - 1] prices[i]);}}return *std::max_element(sell[size - 1].begin(), sell[size - 1].end());}
};
