企业官网建设流程全解析

自媒体 wordpress,太原网站优化多少钱,赚钱黑渠道入口,python 做网站题意 思路一句话概括#xff1a;这是「最多进行 k 次交易」的股票买卖问题#xff0c;可以用三维 DP#xff1a;dp[day][transaction][hold]dp[day][transaction][hold]dp[day][transaction][hold]#xff0c;其中交易数按「卖出次数」计数#xff0c;买入不加 1#xf…题意 思路一句话概括这是「最多进行 k 次交易」的股票买卖问题可以用三维 DPdp[day][transaction][hold]dp[day][transaction][hold]dp[day][transaction][hold]其中交易数按「卖出次数」计数买入不加 1卖出才加 1。leetcode​题目与难点给定整数 k 和数组 pricesprices[i] 表示第 i 天的股价要求在至多 k 笔交易内获得最大利润。leetcode​一次交易 一次买入 一次卖出不能同时持有多笔仓位必须卖了才能再买。leetcode​这题的难点在于既要限制交易次数又要正确处理「持股/不持股」状态。朴素暴力会爆炸需要用状态机 DP 来精确刻画每天的选择。状态设计与含义采用三维 DPdp[i][j]dp[i][j]dp[i][j]第 iii 天结束已经完成了 jjj 次交易且当前 不持股 的最大利润。dp[i][j][2]dp[i][j][2]dp[i][j][2]第 iii 天结束已经完成了 jjj 次交易且当前 持股 的最大利润。关键约定j 表示的是「完成的交易数 完成的 卖出次数」。买入不改变 j。卖出使 j 从 j−1j-1j−1 变成 jjj。这样定义带来的好处交易次数的增加只发生在卖出动作上语义清晰。约束「至多 k 次交易」就变成了 0 j k。初始化细节设day_count pricesSize。transaction_count k 1因为交易数 j 取值范围是 0…k一共 k1 种。leetcode​hold_count 20 表示不持股1 表示持股。初始化三维数组 dp[day_count][transaction_count][2]全部置为一个很小的值 INF_MIN表示「不可能的状态」。leetcode​第 0 天不持股dp0dp 0dp0第 0 天结束不持股且尚未完成任何交易利润为 0。对于 j0j 0j0dp[0][j][0] INF_MIN第 0 天不可能完成任何卖出所以这些都是非法状态。持股dp[2]−pricesdp[2] -pricesdp[2]−prices如果第 0 天结束时选择持股那么唯一方式就是第 0 天买入一次利润为 −prices-prices−prices。对于 j0j 0j0dp[0][j][1] INF_MIN第 0 天不可能既持股又已经完成卖出。注意状态存在并不代表一定会选最终答案是从所有可能状态取最大值。状态转移方程在第 i 天i 1枚举所有交易数 j0…k不持股状态dp[i][j]{dp[i−1],j0max⁡(dp[i−1][j], dp[i−1][j−1][2]prices[i]),j0dp[i][j] \begin{cases} dp[i-1], j 0 \ \max\big(dp[i-1][j],\ dp[i-1][j-1][2] prices[i]\big), j 0 \end{cases}dp[i][j]{dp[i−1],max(dp[i−1][j], dp[i−1][j−1][2]prices[i]),j0j0直观解释j 0还没有完成任何交易所以今天不可能「卖出」只能继承「昨天也不持股」。j 0要么昨天就不持股并且已经完成了 j 次交易今天什么都不做要么昨天持股并完成了 j-1 次交易今天卖出获得 prices[i]完成第 j 次交易。这正体现了「卖出时交易数 1」的逻辑。持股状态dp[i][j][2]max⁡(dp[i−1][j][2], dp[i−1][j]−prices[i])dp[i][j][2] \max\big(dp[i-1][j][2],\ dp[i-1][j] - prices[i]\big)dp[i][j][2]max(dp[i−1][j][2], dp[i−1][j]−prices[i])解释昨天已经持股且完成了 j 次交易今天什么都不做昨天不持股并完成了 j 次交易今天买入一股交易数不变但现金少了 prices[i]。注意这里的关键点买入不改变 j。不能从 dp[i-1][j][1] - prices[i] 来转移否则变成「在已经持股的基础上再买一次」违反「不能同时持有多份股票」的约束。最终答案与遍历顺序当所有天数都算完后最后一天必须是 不持股 状态才能保证利润已经完全兑现。遍历所有 0 j kansmax⁡0≤j≤kdp[day_count−1][j]\text{ans} \max_{0 \le j \le k} dp[day_count-1][j]ans0≤j≤kmaxdp[day_count−1][j]遍历顺序建议外层天数 i 从 1 到 day_count - 1。中层交易数 j 从 0 到 k。边界处理当 j 0 时计算 dp[i][0][0] 不能访问 dp[i-1][-1][1]所以单独特判。其余情况按状态转移方程即可。时间复杂度与空间优化在当前三维 DP 实现中状态数量day_count * (k1) * 2时间复杂度 O(nk)O(nk)O(nk)。空间复杂度同样为 O(nk)O(nk)O(nk)因为 day、transaction、hold 都作为维度存在。优化方向滚动数组转移中 dp[i] 只依赖 dp[i-1]可以把 day 这一维压掉用 dp[transaction_count][2] 来存当前天整体空间降为 O(k)O(k)O(k)。大 k 特判若 k pricesSize / 2则限制形同虚设可以视为「不限次数交易」问题直接用贪心只要 prices[i] prices[i-1] 就把差额加入利润。leetcode​对应 C 实现要点与你的代码对齐你的代码核心部分与上述思路一致关键点包括leetcode​三维 dp 的 malloc 与初始化外三层分别对应 day_count、transaction_count 和 hold_count。每个元素先填充为 INF_MIN代表不可能状态。第 0 天初始化dp[0][0][NOT_HOLD] 0;dp[0][0][HOLD] -prices[0];转移不持股j0只能 dp[i][0][NOT_HOLD] dp[i-1][0][NOT_HOLD];j0dp[i][j][NOT_HOLD]MAX(dp[i-1][j][NOT_HOLD],dp[i-1][j-1][HOLD]price);持股dp[i][j][HOLD]MAX(dp[i-1][j][HOLD],dp[i-1][j][NOT_HOLD]-price);最终答案max_profitINF_MIN;for(j0;jtransaction_count;j)max_profitMAX(max_profit,dp[day_count-1][j][NOT_HOLD]);结束后释放所有 malloc 的内存避免内存泄漏。leetcode​面试官视角下的典型追问在面试场景中如果你给出上述定义和转移面试官很可能继续问你为什么交易次数用「卖出次数」来计而不是买入次数如果要你把三维 DP 优化成二维 / 一维如何改写代码状态遍历顺序会有什么要求当 k 特别大例如 k n/2时有没有必要继续用 O(nk)O(nk)O(nk) 的 DP贪心解法是怎样的leetcode​https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/?envTypestudy-plan-v2envIdtop-interview-150https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/submissions/1875439908/?envTypestudy-plan-v2envIdtop-interview-150