動態(tài)規(guī)劃算法通澈耪恚基于一個轉(zhuǎn)移方程及一個或多個初始狀態(tài)。 當(dāng)前子問題的解將由上一次子問題的解推出眨业。使用動態(tài)規(guī)劃來解題只需要多項(xiàng)式時間復(fù)雜度， 因此它比回溯法沮协、暴力法等要快許多龄捡。

動態(tài)規(guī)劃通常包含最優(yōu)子結(jié)構(gòu)——如果一個問題的最優(yōu)解包含了子問題的最優(yōu)解。

Question 1: 如果我們有面值為1元慷暂、3元和5元的硬幣若干枚聘殖，如何用最少的硬幣湊夠11元？

用d(i)=j來表示湊夠i元最少需要j個硬幣行瑞。我們可以推斷：

• d(0)=0
  • 不需要任何數(shù)量的硬幣
• d(1)=1
  • 這里只有1元硬幣可以選擇 d(1)=d(1-1)+1=d(0)+1=0+1=1
• d(2)=2
  • 這里只有1元硬幣可以選擇 d(2)=d(2-1)+1=d(1)+1=1+1=2
• d(3)=3
  • 這里我們可以選擇3元硬幣或者1元硬幣
  • 如果選擇3元硬幣奸腺，問題就變成1+d(3-3)=1+d(0) = 1+0 = 1
  • 如果選擇1元硬幣，問題就變成1+d(3-1)=1+d(2) = 1+2 = 3
  • 那么這兩種方案那種更好呢血久？ 很明顯第一種突照。min(1+d(0), 1+d(2)) = 1

• d(i)表示湊夠i元需要的最少硬幣數(shù)量，我們將它定義為該問題的”狀態(tài)”氧吐。
• 最終我們要求解的問題讹蘑，可以用這個狀態(tài)來表示：d(11)
• 之前我們提到d(3)=min{d(3-1)+1, d(3-3)+1}，這就是狀態(tài)的轉(zhuǎn)移方程筑舅。
• 那么抽象的轉(zhuǎn)移方程可表示為：d(i)=min{d(i-Vj)+1}座慰，Vj表示第j個硬幣的面值;
• 每個狀態(tài)轉(zhuǎn)移方程都有出口點(diǎn)這里的出口點(diǎn)就是i-Vj<=0.就是一旦滿足這個條件就return 0，結(jié)束遞歸翠拣。

#python
def getMinCoins(value,coins):
    if value<=0:
        return 0
    results=[]
    for coin in coins:
        if value-coin>=0:
            results.append(getMinCoins(value-coin,coins))
    return min(results)+1
coins = [1,3,5]
print(getMinCoins(3,coins))  #ouput = 1
print(getMinCoins(4,coins))  #ouput = 2
print(getMinCoins(11,coins)) #ouput = 3

Java版
public class Main {
    public static void main(String[] args) {
        int[] coins = {1,3,5};
        System.out.println(getMinCoins(3,coins));
        System.out.println(getMinCoins(4,coins));
        System.out.println(getMinCoins(11,coins));
    }
    public static int getMinCoins(int value, int[] coins){
        //程序的出口
        if(value<=0){
            return 0;
        }
        ArrayList results= new ArrayList<Integer>();
        for(int i = 0; i<coins.length;i++){
            if(value-coins[i]>=0)
                results.add(getMinCoins(value-coins[i],coins));
        }
        Collections.sort(results);
        return (int) results.get(0)+1;
    }
}

這里要注意：ArrayList排序的方法

Collections.sort(results);

Question 2 ：一個序列有N個數(shù)：A[1],A[2],…,A[N]版仔，求出最長非降子序列(LIS)的長度。

假設(shè)序列為:

 5心剥，3邦尊，4，8优烧，6蝉揍，7

• 前1個數(shù)的LIS長度d(1)=1(序列：5)
• 前2個數(shù)的LIS長度d(2)=1(序列：5，3——3前面沒有比3小的)
• 前3個數(shù)的LIS長度d(3)=2(序列：5畦娄，3又沾，4——4前面有1個比它小的3，所以d(3)=d(2)+1)
• 前4個數(shù)的LIS長度d(4)=3(序列：5熙卡，3杖刷，4，8——8前面比它小的有3個數(shù)驳癌，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
• 我們可以看出轉(zhuǎn)移方程為：

d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]

• 方程退出遞歸條件為j=0.

#python
def getLIS(list,n):
    if n <=0:
        return 1
    result = [0]
    for i in range(0,n):
        if list[i] < list[n]:
            result.append(getLIS(list,i))
    return max(result)+1

list = [5,3,4,8,6,7]
print(getLIS(list,5))  #ouput is 4