打家劫舍系列

198. 打家劫舍對于當(dāng)前的房間，無非就兩種選擇：偷與不偷。如果當(dāng)前房間偷，那么前一個房間就不偷，即dp[i] = dp[i-2] + nums[i]；如果當(dāng)前房間不偷，那么dp[i] = dp[i-1]，因此遞推公式為：

10余年的蟠龍網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。營銷型網(wǎng)站建設(shè)的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整蟠龍建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“蟠龍網(wǎng)站設(shè)計”,“蟠龍網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

dp[i] = max(dp[i-1],dp[i-2] + nums[i])

213. 打家劫舍 II這個題上上一題的基礎(chǔ)之上加入了成環(huán)的約束條件，因為第一間房間和最后一間房間只能偷一間，因此可以分為兩種情況，一種是不偷第一間房，另一種是不偷最后一間房間，這樣兩種情況都不同考慮成環(huán)的問題且都轉(zhuǎn)化為了上一個題，因此可以用上一個題的思路求解，最終的結(jié)果是兩種情況中的大值。
337. 打家劫舍 III這題將數(shù)組變成了樹，因此涉及到樹的遍歷方式，這里使用后序遍歷。

買賣股票系列

121. 買賣股票的最佳時機這個題只能買賣一次，因此只能在最低點買入，在最低點后的最高點賣出，定義dp數(shù)組dp[i][0]和dp[i][1]，遞推公式如下：

dp[i][0] = min(prices[i],dp[i-1][0]);				//買入時花費的最少現(xiàn)金
dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0]);		//賣出時所得的大利潤

122. 買賣股票的最佳時機 II這個題可以多次買賣，因此在買入的時候還要考慮在此之前花費的現(xiàn)金，遞推公式如下，注意和上一個題遞推公式的差別：

dp[i][0] = min(prices[i] - dp[i-1][1],dp[i-1][0]);  	//買入時花費的最少現(xiàn)金
dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0]);			//賣出時所得的大利潤

123. 買賣股票的最佳時機 III和188. 買賣股票的最佳時機 IV求解思路是一樣的，在只允許買賣兩次的時候就可以發(fā)現(xiàn)規(guī)律，無非就是要列出每天的所有可能狀態(tài)。買賣k次時的代碼實現(xiàn)如下：

class Solution {public:
    int maxProfit(int k, vector& prices) {vector>dp(prices.size(),vector(2 * k + 1));
        //初始化dp數(shù)組
        for(int j = 1 ; j< 2 * k + 1; j += 2) //注意這里是j += 2
            dp[0][j] = -prices[0];  //買入狀態(tài)初始化，賣出狀態(tài)已經(jīng)初始化為0
        //遍歷
        for(int i = 1; i< dp.size(); i++){//dp[i][0] = dp[i-1][0];  //始終保持不變，可以不用
            for(int j = 1; j< 2 * k + 1; j += 2){  //注意這里是j += 2
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i]);    //買入
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j] + prices[i]);  //賣出
            }
        }
        return dp.back()[2*k];
    }
};

當(dāng)j為奇數(shù)的時候表示買入，當(dāng)j為偶數(shù)的時候表示賣出。

309. 最佳買賣股票時機含冷凍期這個題在前四個題的基礎(chǔ)上加入了冷凍期，在求解過程中要理清楚狀態(tài)轉(zhuǎn)移過程，在這個題中定義下面的四個狀態(tài)：

• 狀態(tài)一（ j = 0）：買入狀態(tài)，不一定當(dāng)天買入，也可能是之前就已經(jīng)買入了
• 狀態(tài)二（ j = 1）：賣出狀態(tài)且已經(jīng)度過了冷凍期
• 狀態(tài)三（ j = 2）：今天賣出，還未度過冷凍期
• 狀態(tài)四（j = 3）：冷凍期

根據(jù)狀態(tài)轉(zhuǎn)移關(guān)系即可得到遞推公式：

dp[i][0] = max(dp[i-1][0],max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i]));
dp[i][1] = max(dp[i-1][1],dp[i-1][3]);
dp[i][2] = dp[i-1][0] + prices[i];
dp[i][3] = dp[i-1][2];

714. 買賣股票的最佳時機含手續(xù)費這個題在122. 買賣股票的最佳時機 II的基礎(chǔ)上加入了手續(xù)費，因此在賣出的時候考慮手續(xù)費即可。

子序列問題

子序列問題一定要清楚dp[i]的定義，以及子序列連續(xù)和不連續(xù)的求解區(qū)別。

300. 最長遞增子序列中dp[i]定義為以nums[i]作為子序列的最后一個元素的最長子序列為dp[i]，因此最終的結(jié)果是dp數(shù)組中的大值。核心代碼如下：

for(int i = 1; i< nums.size(); i++){for(int j = 0; j< i; j++){if(nums[i] >nums[j]) dp[i] = max(dp[i],dp[j]+1);
    }
    if(dp[i] >result)  result = dp[i];
}

674. 最長連續(xù)遞增序列這個題要求子序列是連續(xù)的，因此dp[i]只能和dp[i-1]有關(guān)系，遞推公式為：

if(nums[i] >nums[i-1]) dp[i] = dp[i-1] + 1;

如果不滿足nums[i] >nums[i-1]，則dp[i]保持1不變（初始化的時候已經(jīng)賦值為1），因此一個元素就可以構(gòu)成一個子序列。

718. 最長重復(fù)子數(shù)組這個題涉及到兩個數(shù)組，因此要使用二維dp數(shù)組，且dp[i][j]只能由dp[i-1][j-]1得到。如下圖所示：

1143. 最長公共子序列和718. 最長重復(fù)子數(shù)組的區(qū)別在于這題的子序列不連續(xù)，差異主要體現(xiàn)在初始化和遞推公式上，本題的遞推公式為：

if(text1[i] == text2[j])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

dp[i][j]不僅和dp[i-1][j-1]有關(guān)，還和dp[i-1][j]、dp[i][j-1]有關(guān)。

1035. 不相交的線和1143. 最長公共子序列完全一樣，關(guān)鍵是要想明白怎么個一樣法！

53. 大子序和這個題其實就是求的是局部的大和，dp數(shù)組中保存的是局部大和，最終的結(jié)果是dp數(shù)組中的大值，遞推公式如下：

dp[i] = max(dp[i-1] + nums[i],nums[i]);

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：代碼隨想錄訓(xùn)練營第54天|休息日小結(jié)-創(chuàng)新互聯(lián)
分享路徑：http://jinyejixie.com/article40/dsihho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、標(biāo)簽優(yōu)化、全網(wǎng)營銷推廣、做網(wǎng)站、用戶體驗、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)