暴力遞歸：
1.把問題轉化為規(guī)模最小的同類問題的子問題
2.有明確的不需要繼續(xù)進行遞歸的條件（base,case）
3.有當?shù)玫阶訂栴}的結果之后的決策問題
4.不記錄每一個子問題的解

動態(tài)規(guī)劃：
1.從暴力遞歸中來
2.將每一個子問題的解記錄下來，避免重復計算
3.把暴力遞歸的過程，抽象成狀態(tài)表達
4.并且存在化簡狀態(tài)表達，使其更加簡潔

背包問題：

先按照題意暴力遞歸，然后去除題意，改為dp.

給定兩個數(shù)組w和v， 兩個數(shù)組長度相等， w[i]表示第i件商品的
重量， v[i]表示第i件商品的價值。
再給定一個整數(shù)bag， 要求你挑選商品的重量加起來一定不能超
過bag， 返回滿足這個條件下， 你能獲得的最大價值.


package basic_class_07;

public class Code_09_Knapsack {

    public static int maxValue1(int[] c, int[] p, int bag) {
        return process1(c, p, 0, 0, bag);
    }

    public static int process1(int[] c, int[] p, int i, int cost, int bag) {
        if (cost > bag) {
            return Integer.MIN_VALUE;
        }
        if (i == c.length) {
            return 0;
        }
        return Math.max(process1(c, p, i + 1, cost, bag), p[i] + process1(c, p, i + 1, cost + c[i], bag));
    }

    public static int maxValue2(int[] c, int[] p, int bag) {
        int[][] dp = new int[c.length + 1][bag + 1];
        for (int i = c.length - 1; i >= 0; i--) {
            for (int j = bag; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j + c[i] <= bag) {
                    dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[] c = { 3, 2, 4, 7 };
        int[] p = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(maxValue1(c, p, bag));
        System.out.println(maxValue2(c, p, bag));
    }

}

題目：數(shù)組中選和問題

下面代碼中，一種是暴力遞歸，一種是動態(tài)規(guī)劃

給你一個數(shù)組arr， 和一個整數(shù)aim。 如果可以任意選擇arr中的
數(shù)字， 能不能累加得到aim， 返回true或者false



public class Code_08_Money_Problem {

    public static boolean money1(int[] arr, int aim) {
        return process1(arr, 0, 0, aim);
    }

    public static boolean process1(int[] arr, int i, int sum, int aim) {
        if (sum == aim) {
            return true;
        }
        if (i == arr.length) {
            return false;
        }
        return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim);
    }

    public static boolean money2(int[] arr, int aim) {
        boolean[][] dp = new boolean[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][aim] = true;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = aim - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j + arr[i] <= aim) {
                    dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[] arr = { 1, 4, 8 };
        int aim = 12;
        System.out.println(money1(arr, aim));
        System.out.println(money2(arr, aim));
    }

}

最小路徑和問題

下面代碼中一種是暴力遞歸，一種是動態(tài)規(guī)劃

給你一個二維數(shù)組， 二維數(shù)組中的每個數(shù)都是正數(shù)， 要求從左上
角走到右下角， 每一步只能向右或者向下。 沿途經(jīng)過的數(shù)字要累
加起來。 返回最小的路徑和。



public class Code_07_MinPath {

    public static int minPath1(int[][] matrix) {
        return process1(matrix, matrix.length - 1, matrix[0].length - 1);
    }

    public static int process1(int[][] matrix, int i, int j) {
        int res = matrix[i][j];
        if (i == 0 && j == 0) {
            return res;
        }
        if (i == 0 && j != 0) {
            return res + process1(matrix, i, j - 1);
        }
        if (i != 0 && j == 0) {
            return res + process1(matrix, i - 1, j);
        }
        return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
    }

    public static int minPath2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }

    // for test
    public static int[][] generateRandomMatrix(int rowSize, int colSize) {
        if (rowSize < 0 || colSize < 0) {
            return null;
        }
        int[][] result = new int[rowSize][colSize];
        for (int i = 0; i != result.length; i++) {
            for (int j = 0; j != result[0].length; j++) {
                result[i][j] = (int) (Math.random() * 10);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
        System.out.println(minPath1(m));
        System.out.println(minPath2(m));

        m = generateRandomMatrix(6, 7);
        System.out.println(minPath1(m));
        System.out.println(minPath2(m));
    }
}