打家劫舍系列

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

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

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

213. 打家劫舍 II這個題上上一題的基礎之上加入了成環(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];
    }
};

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

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

• 狀態(tài)一（ j = 0）：買入狀態(tài)，不一定當天買入，也可能是之前就已經(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的基礎上加入了手續(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. 最長重復子數(shù)組這個題涉及到兩個數(shù)組，因此要使用二維dp數(shù)組，且dp[i][j]只能由dp[i-1][j-]1得到。如下圖所示：

1143. 最長公共子序列和718. 最長重復子數(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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：代碼隨想錄訓練營第54天|休息日小結(jié)-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/dsihho.html