淮安哪个做网站好点,二手车网站模板建设,济南网站制作工具,南充做网站略奥网络买卖股票最佳时机
I
II 不限制交易次数
prices [7,1,5,3,6,4]
启发思路#xff1a;最后一天发生了什么#xff1f; 从第0天到第5天结束时的利润 从第0天到第4天结束时的利润 第5天的利润 #xff08;第5天的利润#xff1a;0/-4/4#xff09;
关键词#xff1a;天…买卖股票最佳时机
I
II 不限制交易次数
prices [7,1,5,3,6,4]
启发思路最后一天发生了什么 从第0天到第5天结束时的利润 从第0天到第4天结束时的利润 第5天的利润 第5天的利润0/-4/4
关键词天数 / 是否持有股票 分解子问题到第i天结束持有/未持有股票的最大利润 下一子问题到第i-1天结束时持有/未持有股票的最大利润
状态转移图 #mermaid-svg-6kvos0GsmqQmH0yY {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .error-icon{fill:#552222;}#mermaid-svg-6kvos0GsmqQmH0yY .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-6kvos0GsmqQmH0yY .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-6kvos0GsmqQmH0yY .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-6kvos0GsmqQmH0yY .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-6kvos0GsmqQmH0yY .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-6kvos0GsmqQmH0yY .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-6kvos0GsmqQmH0yY .marker{fill:#333333;stroke:#333333;}#mermaid-svg-6kvos0GsmqQmH0yY .marker.cross{stroke:#333333;}#mermaid-svg-6kvos0GsmqQmH0yY svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-6kvos0GsmqQmH0yY .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .cluster-label text{fill:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .cluster-label span{color:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .label text,#mermaid-svg-6kvos0GsmqQmH0yY span{fill:#333;color:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .node rect,#mermaid-svg-6kvos0GsmqQmH0yY .node circle,#mermaid-svg-6kvos0GsmqQmH0yY .node ellipse,#mermaid-svg-6kvos0GsmqQmH0yY .node polygon,#mermaid-svg-6kvos0GsmqQmH0yY .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-6kvos0GsmqQmH0yY .node .label{text-align:center;}#mermaid-svg-6kvos0GsmqQmH0yY .node.clickable{cursor:pointer;}#mermaid-svg-6kvos0GsmqQmH0yY .arrowheadPath{fill:#333333;}#mermaid-svg-6kvos0GsmqQmH0yY .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-6kvos0GsmqQmH0yY .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-6kvos0GsmqQmH0yY .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-6kvos0GsmqQmH0yY .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-6kvos0GsmqQmH0yY .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-6kvos0GsmqQmH0yY .cluster text{fill:#333;}#mermaid-svg-6kvos0GsmqQmH0yY .cluster span{color:#333;}#mermaid-svg-6kvos0GsmqQmH0yY div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-6kvos0GsmqQmH0yY :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 买入 卖出 未持有 持有 定义dfs(i, 0)表示到第i天结束未持有股票的最大利润 定义dfs(i, 1)表示到第i天结束持有股票的最大利润
由于第i-1天的结束就是第i天的开始dfs(i-1, .)也表示到第i天开始时的最大利润
状态转移图中 卖出dfs(i, 0) dfs(i - 1, 1) prices[i] 买入dfs(i, 1) dfs(i - 1, 0) - prices[i] 未持有状态下无动作dfs(i, 0) dfs(i - 1, 0) 持有状态下无动作dfs(i, 1) dfs(i - 1, 1)
汇总公式 dfs(i, 0) max(dfs(i - 1, 0), dfs(i - 1, 1) prices[i]) dfs(i, 1) max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i])
递归边界 dfs(-1, 0) 0 // 第0天开始未持有股票利润为0 dfs(-1, 1) INT_MIN // 第0天开始不可能持有股票
递归入口 max(dfs(n - 1, 0), dfs(n - 1, 1)) dfs(n - 1, 0)
思路
class Solution {
public:// 优化方向改为cacheint dfs(int i, bool hold, const std::vectorint prices) {// 边界if (i 0) {return hold ? INT_MIN : 0;}if (hold) {return max(dfs(i - 1, true, prices), dfs(i - 1, false, prices) - prices[i]);}return max(dfs(i - 1, false, prices), dfs(i - 1, true, prices) prices[i]);}int maxProfit(std::vectorint prices) {int n prices.size();return dfs(n - 1, false, prices);}
};实际代码
class Solution {
public:int maxProfit(std::vectorint prices) {int n prices.size();vectorstd::pairint, int res(n 1);res[0].second INT_MIN;for (auto i 0; i n; i) {res[i 1].first max(res[i].first, res[i].second prices[i]);res[i 1].second max(res[i].second, res[i].first - prices[i]);}return res[n].first;}
};// 演进
class Solution {
public:int maxProfit(std::vectorint prices) {int n prices.size();int f0{};int f1{INT_MIN};for (auto i 0; i n; i) {int new_f0 max(f0, f1 prices[i]);f1 max(f1, f0 - prices[i]);f0 new_f0;}return f0;}
};III 冷冻期 309
class Solution {
public:int maxProfit(std::vectorint prices) {int n prices.size();int f0{-prices.front()};int f1{};int f2{};for (auto i 1; i n; i) {int new_f0 max(f0, f2 - prices[i]);int new_f1 f0 prices[i];int new_f2 max(f1, f2);f0 new_f0;f1 new_f1;f2 new_f2;}return max(f1, f2);}
};IV 最多K次 188
