動态規劃算法常見題型

一、基本概念

動态規劃過程是：每次決策依賴于目前狀态，又随即引起狀态的轉移。一個決策序列就是在變化的狀态中産生出來的，是以，這種多階段最優化決策解決問題的過程就稱為動态規劃。
           

二、基本思想與政策

基本思想與分治法類似，也是将待求解的問題分解為若幹個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。

由于動态規劃解決的問題多數有重疊子問題這個特點，為減少重複計算，對每一個子問題隻解一次，将其不同階段的不同狀态儲存在一個二維數組中。

與分治法最大的差别是：适合于用動态規劃法求解的問題，經分解後得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。

以上都過于理論，還是看看常見的動态規劃問題吧！！！

三、常見動态規劃問題

1.硬币找零問題

詳見http://blog.csdn.net/yyl424525/article/details/55192771

2.求兩字元序列的最長公共字元子序列

問題描述：

字元序列的子序列是指從給定字元序列中随意地（不一定連續）去掉若幹個字元（可能一個也不去掉）後所形成的字元序列。令給定的字元序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴格遞增下标序列i0，i1，…，ik-1，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。

考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：

（1）

如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；

（2）

如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；

（3）

如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。

這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

求解：

引進一個二維數組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS

的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定搜尋的方向。

我們是自底向上進行遞推計算，那麼在計算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來。此時我們根據X[i]

= Y[j]還是X[i] != Y[j]，就可以計算出c[i][j]。

問題的遞歸式寫成：

回溯輸出最長公共子序列過程：

算法分析：

由于每次調用至少向上或向左（或向上向左同時）移動一步，故最多調用(m + n)次就會遇到i = 0或j =

0的情況，此時開始傳回。傳回時與遞歸調用時方向相反，步數相同，故算法時間複雜度為Θ(m + n)。

代碼：

#include <stdio.h>
#include <string.h>
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;

    for(i = ; i <= m; i++)
        c[i][] = ;
    for(j = ; j <= n; j++)
        c[][j] = ;
    for(i = ; i<= m; i++)
    {
        for(j = ; j <= n; j++)
        {
            if(x[i-] == y[j-])
            {
                c[i][j] = c[i-][j-] + ;
                b[i][j] = ;
            }
            else if(c[i-][j] >= c[i][j-])
            {
                c[i][j] = c[i-][j];
                b[i][j] = ;
            }
            else
            {
                c[i][j] = c[i][j-];
                b[i][j] = -;
            }
        }
    }
}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
    if(i ==  || j == )
        return;
    if(b[i][j] == )
    {
        PrintLCS(b, x, i-, j-);
        printf("%c ", x[i-]);
    }
    else if(b[i][j] == )
        PrintLCS(b, x, i-, j);
    else
        PrintLCS(b, x, i, j-);
}

int main(int argc, char **argv)
{
    char x[MAXLEN] = {"ABCBDAB"};
    char y[MAXLEN] = {"BDCABA"};
    int b[MAXLEN][MAXLEN];
    int c[MAXLEN][MAXLEN];
    int m, n;

    m = strlen(x);
    n = strlen(y);

    LCSLength(x, y, m, n, c, b);
    PrintLCS(b, x, m, n);

    return ;
}

           

Java版

import java.util.Scanner;
//最長公共子序列
//c[i][j]記錄x[i]與y[j]的LCS的長度，b[i][j]記錄c[i][j]是通過哪個子問題的解得到的，以決定搜尋方向
public class Lcs {
    static int b[][],c[][];
    static int m,n;
    static String xString,yString;
    public static void main(String [] args){
     Scanner scanner=new Scanner(System.in);
      xString=scanner.nextLine();
      yString=scanner.nextLine();
     m=xString.length();
     n=yString.length();
     b=new int[m+1][n+1];
     c=new int[m+1][n+1];

     getLcs();
     printLcs(m,n);
    }

    private static void printLcs(int m,int  n) {
                if(m==0||n==0)
                    return ;
                if(b[m][n]==1)
                {
                    printLcs(m-1, n-1);
                    System.out.print(xString.charAt(m-1));
                }
                else if(b[m][n]==2)
                {
                    printLcs(m, n-1);
                }else if(b[m][n]==3)
                {
                    printLcs(m-1, n);
                }
    }

    private static void getLcs() {

        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(xString.charAt(i-1)==yString.charAt(j-1))
                {
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }else if(c[i][j-1]>=c[i-1][j])
                {
                    c[i][j]=c[i][j-1];
                    b[i][j]=2;
                }else {
                    c[i][j]=c[i-1][j];
                    b[i][j]=3;
                }
            }
        }

    }
}
           

3.走台階問題

有n級台階，一個人每次上一級或者兩級，問有多少種走完n級台階的方法。為了防止溢出，請将結果Mod 1000000007

給定一個正整數int n，請傳回一個數，代表上樓的方式數。保證n小于等于100000。

測試樣例：

1

傳回：1

解析： 設DP[i]為走到第i層一共有多少種方法，那麼DP[80]即為所求。很顯然DP[1]=1, DP[2]=2（走到第一層隻有一種方法：就是走一層樓梯；走到第二層有兩種方法：走兩次一層樓梯或者走一次兩層樓梯）。同理，走到第i層樓梯，可以從i-1層走一層，或者從i-2走兩層。很容易得到：

// 遞推公式：DP[i]=DP[i-1]+DP[i-2]

// 邊界條件：DP[1]=1 DP[2]=2

public class ClimbStairs {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        System.out.println(climbStair(n));
        System.out.println(climbStair2(n));
    }
//自頂向下一般采用遞歸
    private static int climbStair(int n) {
        if(n==)
            return ;
        if(n==)
            return ;
        else return climbStair(n-)+climbStair(n-);
    }
    //自頂向上一般采用數組填表方式
    private static int climbStair2(int n)
    {
        int []temp=new int[n+];
        temp[]=;
        temp[]=;
        for (int i = ; i <=n ; i++) {
            temp[i]=temp[i-]+temp[i-];
        }
        return temp[n];
    }
}