概念

說到動(dòng)態(tài)規(guī)劃，什么是動(dòng)態(tài)規(guī)劃？

動(dòng)態(tài)規(guī)劃（英語：Dynamic programming，簡(jiǎn)稱 dp）通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。

看著這么復(fù)雜哈，其實(shí)總結(jié)出來就是大事化小，拆分成小問題但是這些小問題和原問題是同質(zhì)的，動(dòng)規(guī)致力于解決每一個(gè)子問題，減少計(jì)算，其實(shí)和遞歸思想，分治法有些類似，斐波那契數(shù)列就可以看做入門級(jí)的經(jīng)典動(dòng)規(guī)問題

這里引用一個(gè)網(wǎng)上流行的例子來給大家體會(huì)一下：

A ：“1+1+1+1+1+1+1+1 =？”
A ：“上面等式的值是多少”
B ：計(jì)算 “8”
A : 在上面等式的左邊寫上 “1+” 呢？
A : “此時(shí)等式的值為多少”
B : 很快得出答案 “9”
A : “你怎么這么快就知道答案了”
A : “只要在8的基礎(chǔ)上加1就行了”
A : “所以你不用重新計(jì)算，因?yàn)槟阌涀×说谝粋€(gè)等式的值為8!動(dòng)態(tài)規(guī)劃算法也可以說是 ‘記住求過的解來節(jié)省時(shí)間’”

性質(zhì)

1.最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理（說人話就是切大瓜，切到最小又不影響我體驗(yàn)）

2.有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到（說人話就是藕斷絲連，拿一個(gè)可能帶動(dòng)其他）

3.無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)（說人話就是把水化成冰，但本質(zhì)上依然是水）

典型特征

動(dòng)態(tài)規(guī)劃有4個(gè)典型特征：

1.最優(yōu)子結(jié)構(gòu)

2.狀態(tài)轉(zhuǎn)移方程

3.邊界

4.重疊子問題

以我們熟悉的斐波那契數(shù)列為例

f(n-1)和f(n-2) 稱為 f(n) 的最優(yōu)子結(jié)構(gòu)，f(n)= f（n-1）+f（n-2）就稱為狀態(tài)轉(zhuǎn)移方程，f(1) = 1, f(2) = 2 稱為邊界，其中f(5)= f(4)+f(3),f(4) = f(3) + f(2) ,f(3)就是重疊子問題。

實(shí)戰(zhàn)論證

要學(xué)習(xí)dp算法就一定得談?wù)?LeetCode 里面的鼻祖題——炒股系列問題，我們就拿例題來港港怎么理解他的典型特征

初始題比較簡(jiǎn)單，我們以 II 為例：

示例：
輸入: prices = [7,1,5,3,6,4]
輸出: 7

小捷徑

看到這里其實(shí)最簡(jiǎn)單的方法已經(jīng)明了了，那就是貪心算法，只要能賺，只要不賠我就買買買！你說我貪不貪心？

int maxProfit(int* prices, int pricesSize) {
    int sum = 0;
    for (int i = 1; i < pricesSize; ++i) {
        sum += fmax(0, prices[i] - prices[i - 1]);
    }
    return sum;
}

這里用了一個(gè)庫函數(shù) fmax ，需要引頭文件<math.h>，用于比較兩個(gè)參數(shù)的最大值，語法是：

type fmax  (參數(shù)1 , 參數(shù)2);

再介紹一種我自己用的方法，和貪心原理上差不多，只是用的普普通通的遍歷：

int maxProfit(int* prices, int pricesSize) {
	int n = 0;
	if (pricesSize == 0)
	{
		return 0;
	}
	int sum = 0;
	while (n < pricesSize - 1)
	{
		for (n = 0; n < pricesSize - 1; n++)
			if (prices[n + 1] - prices[n] > 0)//保證買賣能賺就入手
			{
				sum += prices[n+1]-prices[n];
			}
	}
	return sum;
}

我自己的方法還是比較優(yōu)的

這樣就能一套帶走，但我們要用 dp 去搞定他，dp 其實(shí)也很簡(jiǎn)單，只是看著有點(diǎn)復(fù)雜，咱不能望而卻步是吧。

分析條件，題目中說不能多次買賣，那我們有且只有兩種狀態(tài)就是沒有和有一支，沒有就是手里為0，又有兩種可能就是前一天就是 0 和這一天有一支但被賣出去了；同理，有一支的情況就是前一天就有一支和前一天兩手空空但我今天買進(jìn)了一支。以此我們寫出求最大利潤(rùn)的狀態(tài)轉(zhuǎn)移方程( i 從 0 開始)：

第i天有0支股票：dp[i][0] = dp[i-1][0] + dp[i][1]+prices[i];
第i天有1支股票：dp[i][1] = dp[i-1][1] + dp[i-1][0]-prices[i];

狀態(tài)轉(zhuǎn)移方程寫出來了，題目就迎刃而解了

算法實(shí)現(xiàn)

1、借助數(shù)組或者二維數(shù)組，保存每一個(gè)子問題的結(jié)果，具體創(chuàng)建數(shù)組還是二維數(shù)組看題目而定，比如找零錢問題中的不同面值零錢與總錢數(shù)，這樣就需要?jiǎng)?chuàng)建一個(gè)二維數(shù)組

2、對(duì)應(yīng)題干條件，具體要求來設(shè)置數(shù)組邊界值,一維數(shù)組就是設(shè)置第一個(gè)數(shù)字，二維數(shù)組就是設(shè)置第一行跟第一列的值

3、找出狀態(tài)轉(zhuǎn)換方程，找到每個(gè)狀態(tài)跟他上一個(gè)狀態(tài)的關(guān)系，根據(jù)狀態(tài)轉(zhuǎn)化方程就可以寫出代碼

我們用剛剛推出來的狀態(tài)轉(zhuǎn)移方程就可以寫出整個(gè)代碼框架：

int maxProfit(int* prices, int pricesSize) {
    int sz = pricesSize;
    int i = 0;
    int dp[sz][2] = 0; //sz是最大買賣天數(shù)內(nèi)的價(jià)格，2代表兩種狀態(tài)0和1
    dp[0][0] = 0,dp[0][1]=-prices[0];//設(shè)置邊界值
    for(i=0;i<sz;i++)
    {
    dp[i][0] = fmax(dp[i-1][0] + dp[i][1]+prices[i]);
    dp[i][1] = fmax(dp[i-1][1] + dp[i-1][0]-prices[i]);//兩種狀態(tài)分別求最大利潤(rùn)
    }
    return [sz-1][0];
  }

優(yōu)化

我們不難發(fā)現(xiàn)，我們的收益只和股票前一天的價(jià)格掛鉤，和更早的狀態(tài)沒有關(guān)系，那我們?yōu)榱藴p小時(shí)間復(fù)雜度和空間復(fù)雜度，可以將二維數(shù)組轉(zhuǎn)化成一維滾動(dòng)數(shù)組搞定

int maxProfit(int* prices, int pricesSize) {
    int dp[pricesSize][2];
    int dp0 = 0;dp1 = -prices[0];
    for (int i = 1; i < pricesSize; ++i)
     {
       int Dp0 = fmax(dp0, dp1+prices[i]);
        Dp1 = fmax(dp1, dp0-prices[i]); //同理轉(zhuǎn)換出狀態(tài)轉(zhuǎn)移方程
    }
    dp0 = Dp0;
    dp1 = Dp1;//滾動(dòng)更新dp0和dp1
    return dp[pricesSize - 1][0];
}

好了，今天就先到這里，摸了家人們，更多關(guān)于C語言動(dòng)態(tài)規(guī)劃點(diǎn)殺dp算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論