動態(tài)規(guī)劃：把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解

動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。當前子問題的最優(yōu)解將由上一次子問題的解推出。使用動態(tài)規(guī)劃來解題只需要多項式時間復(fù)雜度，因此它比回溯法、暴力法等要快許多。

與分治法的區(qū)別：

分治法將分解后的子問題看成相互獨立的，通過用遞歸來做。

動態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系,有重疊部分，需要記憶，通常用迭代來做。

1. 硬幣問題

/**
 * 如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？
 * dp[i] = j 表示i元錢需要j個硬幣
 * 公式: dp[i] = min{dp[i-j] + 1}
 * 初始狀態(tài): dp[0] = 0
 */
public class DpCoins {

    public static void main(String[] args) {
        int[] coins = {1, 3, 5};
        int sumMoney = 11;
        int[] dp = new int[12];
        // 初始化每個價格需要的最大硬幣數(shù)量
        for(int i = 0; i < 12; i++) {
            dp[i] = i;
        }
        for (int i = 1; i < 12; i++) {
            for (int j = 0; j < 3; j++) {
                // 如果dp[i] > dp[i-j]+1，替換
                if (i >= coins[j] && dp[i] > dp[i - coins[j]] + 1) {
                    dp[i] = dp[i - coins[j]] + 1;
                }
            }
        }
        for (int i = 0; i < 12; i++) {
            System.out.println("dp[" + i + "] = " + dp[i]);
        }
    }
}

2. 跳臺階問題

/**
 * 有n級臺階，一個人每次上一級或者兩級，有多少種走完n級臺階的方法
 * dp[n] = m表示走n級臺階有m中方法
 * 遞推公式 dp[n] = dp[n-1] + dp[n-2]
 * 初始條件 dp[1] = 1, dp[2] = 2
 */
public class DpSteps {

    public static int step(int n) {
        int[] everySteps = {1, 2};
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(step(5));
    }
}

3. 割鋼條收益問題

將鋼條切割為長度是len1，len2，…，lenk的小段，得到最大收益

image.png

public class DpCutRod {
    public static int cutRod(int[] lengthPrice, int rodLength) {
        int[] rodPrice = new int[rodLength + 1];
        // 初始化
        for (int i = 0; i <= rodLength; i++) {
            rodPrice[i] = 0;
        }
        if (rodLength == 0) {
            return 0;
        }
        for (int i = 1; i < rodPrice.length; i++) {
            for (int j = 0; j < lengthPrice.length; j++) {
                if (i >= (j + 1) && rodPrice[i] < rodPrice[i - (j + 1)] + lengthPrice[j]) {
                    rodPrice[i] = rodPrice[i - (j + 1)] + lengthPrice[j];
                }
            }
        }
        return rodPrice[rodLength];
    }

    public static void main(String[] args) {
        int[] lengthPrice = {1,5,8,9,10,17};
        int rodLength = 25;
        System.out.println(cutRod(lengthPrice, rodLength));
    }
}