概念

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

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

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

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

A ：“1+1+1+1+1+1+1+1 =？”
A ：“上面等式的值是多少”
B ：計算 “8”
A : 在上面等式的左邊寫上 “1+” 呢？
A : “此時等式的值為多少”
B : 很快得出答案 “9”
A : “你怎么這么快就知道答案了”
A : “只要在8的基礎(chǔ)上加1就行了”
A : “所以你不用重新計算，因為你記住了第一個等式的值為8!動態(tài)規(guī)劃算法也可以說是 ‘記住求過的解來節(jié)省時間’”

性質(zhì)

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

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

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

典型特征

動態(tài)規(guī)劃有4個典型特征：

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)就是重疊子問題。

實戰(zhàn)論證

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

初始題比較簡單，我們以 II 為例：

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

小捷徑

看到這里其實最簡單的方法已經(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;
}

這里用了一個庫函數(shù) fmax ，需要引頭文件<math.h>，用于比較兩個參數(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 其實也很簡單，只是看著有點復(fù)雜，咱不能望而卻步是吧。

分析條件，題目中說不能多次買賣，那我們有且只有兩種狀態(tài)就是沒有和有一支，沒有就是手里為0，又有兩種可能就是前一天就是 0 和這一天有一支但被賣出去了；同理，有一支的情況就是前一天就有一支和前一天兩手空空但我今天買進了一支。以此我們寫出求最大利潤的狀態(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)移方程寫出來了，題目就迎刃而解了

算法實現(xiàn)

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

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

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

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

int maxProfit(int* prices, int pricesSize) {
    int sz = pricesSize;
    int i = 0;
    int dp[sz][2] = 0; //sz是最大買賣天數(shù)內(nèi)的價格，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)分別求最大利潤
    }
    return [sz-1][0];
  }

優(yōu)化

我們不難發(fā)現(xiàn)，我們的收益只和股票前一天的價格掛鉤，和更早的狀態(tài)沒有關(guān)系，那我們?yōu)榱藴p小時間復(fù)雜度和空間復(fù)雜度，可以將二維數(shù)組轉(zhuǎn)化成一維滾動數(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;//滾動更新dp0和dp1
    return dp[pricesSize - 1][0];
}

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

最新評論