动态规划 - 简书

动态规划

image.png

EG1：

题目：

image.png

思路1：先用递归，比如我要求i,j位置的值，那么无非两种情况，到(i,j)位置的最小值不是从上面来的就是从左边来的，所以就可以抽象成F(i,j) = （i,j）位置的值+Math.min(上，左)，注意，因为起始的i,j位置是最右下角的位置，所以basecase是i和j都等于0的时候。

代码1：

    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));
    }

思路2：

运用动态规划，我们在递归的时候了解到，（i,j）位置的值依赖它左边或者上边的值，所以我们就先把它依赖的求出来，然后从左上开始向（i,j）求，相当于把递归的过程反过来。申请一个新的二维数组空间，分别求出第一行和第一列的累计和的值，然后再求（i,j）位置的值时就可以根据已经求出的第一行和第一列的累计和来算（把每个i,j位置的路径和都算出来），先找出不被依赖的，再求出依赖的。

代码2：

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];
    }

EG2:

题目：

image.png

思路1：

递归：即对于每个数选或者不选，当前位置的累加和等与之前的加当前位置，有两个变量，i，sum，sum表示在i前做出的决定已经累加的值，i代表下标。递归即可（类似递归模块的例子）所以，在每个位置的sum有两个选择1.sum+当前位置即选了，2.sum不加即不选

代码1：

image.png

总结：你的解空间定了，尝试函数一旦定了，所有空间就能列出来，空间里，普遍位置依赖啥，逆着算就得出答案，即你递归的时候i,sum是变得，根据i,sum的范围列出空间表

最后编辑于：2018.01.16 21:43:10