做母嬰的網(wǎng)站有哪些,自己建設(shè)網(wǎng)站教程,wordpress 酒店預(yù)定,誘導(dǎo)網(wǎng)站怎么做不涉及題目講解#xff0c;只介紹題目中容易踩的坑#xff01;#xff01;#xff01; 1、dp[j][0]和dp[j][1]的更新順序?yàn)槭裁礇]要求#xff1f; 2、為什么最多 k 次交易的股票 DP 不需要對(duì) k 倒序遍歷#xff1f;一、先明確 DP 的定義#xff08;這是一切的前提#…不涉及題目講解只介紹題目中容易踩的坑1、dp[j][0]和dp[j][1]的更新順序?yàn)槭裁礇]要求2、為什么最多 k 次交易的股票 DP 不需要對(duì) k倒序遍歷一、先明確 DP 的定義這是一切的前提代碼中 DP 的含義是dp[j][0]在「最多 j 次交易」的限制下不持股的最大利潤(rùn) dp[j][1]在「最多 j 次交易」的限制下持股的最大利潤(rùn)?? 關(guān)鍵在于這四個(gè)字最多 j 次交易而不是「已經(jīng)完成 j 次交易」。這是后面所有結(jié)論的根源。二、狀態(tài)轉(zhuǎn)移回顧每天價(jià)格為price轉(zhuǎn)移方程是dp[j][1]max(dp[j-1][0]-price,# 今天買入dp[j][1]# 之前就持有)dp[j][0]max(dp[j][1]price,# 今天賣出dp[j][0]# 之前就不持有)這里有兩個(gè)看起來“危險(xiǎn)”的點(diǎn)dp[j][1]用到了dp[j-1][0]dp[j][0]又用到了本輪更新后的dp[j][1]按很多 DP 的經(jīng)驗(yàn)這似乎會(huì)導(dǎo)致狀態(tài)污染。但實(shí)際上不會(huì)。三、第一個(gè)疑問本輪dp[j][1]被dp[j][0]使用安全嗎假設(shè)dp[j][1]是剛更新的dp[j][1]dp[j-1][0]-price那么dp[j][0]中的這一項(xiàng)就是dp[j][1]price(dp[j-1][0]-price)pricedp[j-1][0]這意味著什么同一天買入 同一天賣出 什么都沒做利潤(rùn)不會(huì)增加交易次數(shù)也不會(huì)被“白嫖”所以即便用了本輪的dp[j][1]也只是一個(gè)無效操作不會(huì)破壞結(jié)果。四、核心原因j 表示的是「最多」不是「已經(jīng)用掉」這是最重要的一點(diǎn)。1?? 如果 j 表示「已經(jīng)完成 j 次交易」那么dp[j]一定嚴(yán)格依賴dp[j-1]正序遍歷會(huì)讓一次交易被重復(fù)使用必須倒序這就和 0/1 背包是完全一致的。2?? 但這道題里j 表示「最多 j 次交易」這意味著dp[j] ≥ dp[j-1]多給一次交易額度只會(huì)讓解更好或不變用到「本輪更新的 dp[j-1]」依然是合法狀態(tài) 不存在“交易次數(shù)被重復(fù)消費(fèi)”的問題。五、為什么正序遍歷不會(huì)“超額交易”假設(shè)我們正序遍歷j 1 → 2 → 3當(dāng)我們計(jì)算dp[2]時(shí)用到的dp[1]表示的是在當(dāng)前天結(jié)束時(shí)最多 1 次交易的最優(yōu)狀態(tài)用這個(gè)狀態(tài)再買一次得到的是「最多 2 次交易」? 完全合法而不是“已經(jīng)完成 1 次交易再偷偷多用一次”六、和「必須倒序」的股票 DP 對(duì)比如果我們把定義改成dp[j][0]已經(jīng)完成 j 次交易不持股 dp[j][1]已經(jīng)完成 j 次交易持股那么轉(zhuǎn)移會(huì)變成dp[j][1]max(dp[j][1],dp[j][0]-price)dp[j][0]max(dp[j][0],dp[j][1]price)此時(shí)dp[j]依賴dp[j]正序遍歷一定出錯(cuò)必須倒序遍歷 j 是否倒序完全取決于 j 的語義而不是題目是不是“股票”。七、總結(jié)給以后的自己是否需要對(duì) k 倒序遍歷關(guān)鍵不在于 DP 的形式而在于 j 表示什么。j 的含義是否需要倒序已經(jīng)用掉 j 次交易? 必須倒序最多允許 j 次交易? 可以正序再補(bǔ)一句非常重要的經(jīng)驗(yàn)在「最多 k 次交易」的股票 DP 中即便同一天發(fā)生“買入 → 賣出”也只會(huì)產(chǎn)生 0 利潤(rùn)不會(huì)破壞狀態(tài)。