動(dòng)態(tài)規(guī)劃的算法本質(zhì)

• 本質(zhì)上就是窮舉狀態(tài)，然后在選擇中選擇最優(yōu)解
• 你只要記住狀態(tài)和選擇兩個(gè)詞即可

以上面的題目為例子

窮舉框架

dp[i][k][0 or 1] 0 <= i <= n - 1, 1 <= k <= K n 為天數(shù)，大 K 為交易數(shù)的上限，0 和 1 代表是否持有股票。 此問(wèn)題共 n × K × 2 種狀態(tài)，全部窮舉就能搞定。for 0 <= i < n:for 1 <= k <= K:for s in {0, 1}:dp[i][k][s] = max(buy, sell, rest)

狀態(tài)轉(zhuǎn)移框架

• 持有狀態(tài)的狀態(tài)轉(zhuǎn)移圖片
  

• 其實(shí)后一天的股票盈利模式都是由前一天得到的，可以在前一天的基礎(chǔ)上來(lái)得到的

121.買賣股票的最佳時(shí)機(jī) I

重點(diǎn)：在某一天選擇買入這只股票，并選擇在未來(lái)某一個(gè)不同的日子賣出該股票。是書(shū)寫狀態(tài)轉(zhuǎn)移方程的關(guān)鍵！

代碼實(shí)現(xiàn)

class Solution {public int maxProfit(int[] prices){// 對(duì)于狀態(tài)轉(zhuǎn)移來(lái)講，最關(guān)鍵是搞出狀態(tài)轉(zhuǎn)移方程int n = prices.length;// 創(chuàng)建dp數(shù)組用于存儲(chǔ)狀態(tài)轉(zhuǎn)移方程int[][] dp = new int[n][2];// 循環(huán)進(jìn)行狀態(tài)轉(zhuǎn)移變換for(int i = 0; i < n; i++){if(i - 1 == -1){// 基本的狀態(tài)轉(zhuǎn)移方程dp[i][0] = 0; // 剛開(kāi)始表示沒(méi)有持有股票，dp[i][1] = -prices[i]; // 為1的時(shí)候肯定是持有股票，還沒(méi)有將股票賣出// 為了提高效率，肯定是需要在進(jìn)行本輪賦值結(jié)束以后，使用continue終止本輪 i - 1 == -1 的操作continue;}// 并不是在if條件的反面才進(jìn)行狀態(tài)轉(zhuǎn)移方程的書(shū)寫dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 前一天沒(méi)有 以及 前一天擁有并賣出進(jìn)行比較dp[i][1] = Math.max(dp[i-1][1], -prices[i]); // dp[i-1][0] 因?yàn)闆](méi)有持有肯定為0}// 要想凈值最大，肯定是看在最后一天，且股票已經(jīng)賣出狀態(tài)下的值return dp[n-1][0];} }

122 買賣股票的最佳時(shí)機(jī) II

***重點(diǎn)：***任何時(shí)候最多只能持有一股股票，同一天可以進(jìn)行購(gòu)買并出售

代碼實(shí)現(xiàn)

class Solution {public int maxProfit(int[] prices) {// 可以使用動(dòng)態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移方程來(lái)進(jìn)行書(shū)寫int n = prices.length;int[][] dp = new int[n][2];for(int i = 0; i < n; i++){if(i - 1 == -1){dp[i][0] = 0;dp[i][1] = -prices[i]; // 1表示現(xiàn)在已經(jīng)買了continue;}dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 當(dāng)天的股票和前一天的兩種情況進(jìn)行相應(yīng)比較即可dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // dp[i-1][0] - prices[i]前一天沒(méi)有股票，后一天有股票，表示已經(jīng)買了股票了}return dp[n-1][0];} }

123.買賣股票的最佳時(shí)機(jī) III

代碼實(shí)現(xiàn)

class Solution {public int maxProfit(int[] prices) {// 理解題目的意思，這里的k的定義并不是(已進(jìn)行的交易次數(shù))，而是最大交易次數(shù)的上線限制// 如果確定今天進(jìn)行一次交易，要保證截止今天最大交易次數(shù)上限為k，那么昨天的最大交易次數(shù)上線為 k-1int max_k = 2;int n = prices.length;int[][][] dp = new int[n][max_k + 1][2];// 內(nèi)容都是一樣的for(int i = 0; i < n; i++){for(int k = max_k; k > 0; k--){// baseif(i - 1 == -1){dp[i][k][0] = 0;dp[i][k][1] = -prices[i]; // 第一天擁有的話，肯定是將股票進(jìn)行買入了continue;}// 進(jìn)行狀態(tài)轉(zhuǎn)移方程更新dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); // 前一天有k次，但是都已經(jīng)賣出去了dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); // 前一天沒(méi)有，經(jīng)過(guò)購(gòu)買股票，使得后一天就有了}}return dp[n-1][max_k][0]; // 通過(guò)循環(huán)來(lái)進(jìn)行比較也清楚最后肯定是在n-1處} }

總結(jié)

以上是生活随笔為你收集整理的动态规划 - 买卖股票的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。