代碼隨想錄訓練營第54天|休息日小結-創(chuàng)新互聯(lián)

打家劫舍系列

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

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

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

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

買賣股票系列

121. 買賣股票的最佳時機這個題只能買賣一次，因此只能在最低點買入，在最低點后的最高點賣出，定義dp數組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數組
        for(int j = 1 ; j< 2 * k + 1; j += 2) //注意這里是j += 2
            dp[0][j] = -prices[0];  //買入狀態(tài)初始化，賣出狀態(tài)已經初始化為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為奇數的時候表示買入，當j為偶數的時候表示賣出。

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

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

根據狀態(tài)轉移關系即可得到遞推公式：

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]，因此最終的結果是dp數組中的大值。核心代碼如下：

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]有關系，遞推公式為：

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

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

718. 最長重復子數組這個題涉及到兩個數組，因此要使用二維dp數組，且dp[i][j]只能由dp[i-1][j-]1得到。如下圖所示：
在這里插入圖片描述
1143. 最長公共子序列和718. 最長重復子數組的區(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]有關，還和dp[i-1][j]、dp[i][j-1]有關。

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

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

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

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

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

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

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

猜你還喜歡下面的內容