动态规划：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的最优解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

与分治法的区别：

分治法将分解后的子问题看成相互独立的，通过用递归来做。

动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。

1. 硬币问题

/**
 * 如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
 * dp[i] = j 表示i元钱需要j个硬币
 * 公式: dp[i] = min{dp[i-j] + 1}
 * 初始状态: 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];
        // 初始化每个价格需要的最大硬币数量
        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));
    }
}