相关文章：

在上一篇文章中，我们从dfs - 记忆化搜索 - 动态规划3步骤来解决了关于路径问题的相关算法题，其实我们在实际的面试场景中，常见的使用动态规划的题目有：

• 坐标类问题 例如 一维数组和二维数组
• 前缀类问题 例如一个字符串划分，两个字符串匹配等
• 背包类问题 这个是常考的题目。

除此之外，还有区间型问题、博弈型问题、树型问题、状态压缩型，这几类问题考的很少，基本不考，因此我们需要关注前3类问题，注重解题技巧。

那么动态规划最难点在于状态数组dp的表示方法，像二维数组，我们通过dp[i][j]来表示，而不同类型的问题，dp的表示方式不一样，所以拿到题目对应到题目类型很重要。

1 常见的动态规划问题

1.1 坐标型动态规划

对于此类问题，例如一维数组，那么就需要定义dp[i]，代表从起点到坐标i的最优解/方案数/可行性；例如二维数组，那么就需要定义dp[i][j]，代表从起点到坐标i，j的最优解/方案数/可行性。

代表性的题目：数字三角形、矩阵最短路径和、机器人路径数（Unique Paths）等。

1.2 前缀型动态规划

对于划分型问题，dp[i]代表前i个字符串的最优解/方案数；dp[i][j]代表前i个字符串划分为j个部分的最优解/方案数/可行性。

对于匹配型问题，dp[i][j]代表第一个字符串的前i个字符，匹配上第二个字符串的前j个字符的最优解/方案数/可行性。

1.3 背包型动态规划

对于背包型动态规划，dp[i][j]代表从前i个物品中取出一些物品组成和为j的最优解/方案数/可行性。

这里和前面两种题目的不同之处在于，j不再代表位置信息，而是和。

2 坐标型动态规划

2.1 跳跃问题

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入： nums = [2,3,1,1,4]
输出： true
解释： 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入： nums = [3,2,1,0,4]
输出： false
解释： 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

分析

从题意中可以看到，这个一个需要求可行性的问题，而且是一维数组具备方向性，所以满足动态规划问题的条件。

首先这道题中，数组每个值代表能够跳动的最长距离，既可以跳1步，也可以跳N步，我们在遍历每一个数组元素的时候，都需要从dp里判断是否能够到达i，例如当i = 4时，此时前面所有的都可达，但i=3时不能跳，且3之前所有的元素都可达，因此无法跳到i= 4的位置。

public boolean canJump(int[] nums) {
    if(nums == null || nums.length == 0){
        return false;
    }

    //state
    // 状态数组标记，从起点到任意一点是否可跳过去
    boolean[] dp = new boolean[nums.length];
    //init
    dp[0] = true; //第一步一定能到
    for(int i = 1;i < nums.length;i++){
        //坐标位置 第i个位置，看是否能够从起点到这个位置
        for(int j = 0;j < i;j++){
            //判断当前j是否能够跳到 i
            // 这里为什么＋j，是因为在j这个位置前面是可达的，需要加上前面的步数
            if(dp[j] && nums[j] + j >= i){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[nums.length-1];
}

3 背包型动态规划

我们从几个经典的背包问题，来总结背包型的动态规划如何解决。

2.1 01 背包问题

给定一个数组，数组中每个值代表物品的大小，能否挑出一些物品装满大小为m的背包。

分析

这个是经典的背包问题，例如数组[3,5,2,7]，当然数组不是排好序的，这个没有强制的规定，背包大小为11，当然不一定满足总数一定等于11，可以说是 <= 11，从中取最接近11的方案。

那么接近12的方案有：[3] , [5] , [2], [7] , ... [3,5,2]，那么其中最节接近的是最后一个，所以相当于从所有的方案中取最优解，那么符合动态规划的问题。

什么是01背包，就是一个物品只能选择一次，要或者不要，如果一个物品可以选多次，那么就是多重背包问题。

看下二维数组，行代表所有物品的重量，每一列代表重量和，定义状态数组dp[i][j]代表前i个物品是否可以装满重量为j的背包。

public static boolean backpack(int[] nums, int w) {

    //背包问题
    if (nums == null || nums.length == 0) {
        return false;
    }

    //state

    //dp[i][j] 代表前i个物品是否能够装满重量为j的背包
    int[][] dp = new int[nums.length][w + 1];
    //前0个物品，是否能够装满重量为1的背包，肯定可以  1 true 0 false
    dp[0][0] = 1;

    //init
    for (int i = 1; i <= w; i++) {
        //前0个物品，都不能装满超过重量1的背包
        dp[0][i] = 0;
    }

    for (int i = 1; i < nums.length; i++) {
        //前i个物品，都能装满重量为0的背包
        dp[i][0] = 1;
    }

    for (int i = 1; i < nums.length; i++) {
        //前i个物品
        for (int j = 1; j <= w; j++) {
            //重量
            if (nums[i] >= j) {
                //自身就能装满背包
                dp[i][j] = 1;
            } else {
                //如果自身无法装满背包，需要查之前的物品是否可以装满剩余的空间
                if (dp[i - 1][j - nums[i]] == 1) {
                    dp[i][j] = 1;
                }
            }
        }
    }
    return dp[nums.length - 1][w] == 1;
}

首先初始化dp数组，首先第一行和第一列都可以先初始化，第一行代表，前0个数字是否可以装满[0,w]容量的背包，1代表可以，0代表不可以，显然在容量超过1之后的，都不可以。

那么第一列代表前i个物品，是否可以装满容量为0的背包，显然可以。

接下来就行填剩余格子的状态，首先如果当前第i个物品自身的重量就已经可以装满那么就置为1，如果当前物品的自身重量无法装满，那么就看前面的物品是否可以填满剩余的空间。例如第2个元素自身重量为5，那么在dp[2][6]时就无法填满背包，剩余重量为1，那么就去前i-1个元素查看状态，在dp[1][1]中看到，状态为1，意味着可以填满，所以此时dp[2][6]的状态也为1.

2.1.1 最优解问题，求最多能装多满

在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m。

前面的算法，我们没有处理溢出的边界case，那么这个问题是最多能装多满，不能溢出，看下决策树。

定义状态数组dp[i][j]，代表前i个物品最多装满j容器的背包总数，那么第一行和第一列肯定都无法装入数字，初始化为0.

public static int backpack2(int[] nums, int w) {

    //背包问题
    if (nums == null || nums.length == 0) {
        return 0;
    }

    //state

    //dp[i][j] 代表前i个物品最多能够装满重量为j的背包
    int[][] dp = new int[nums.length + 1][w + 1];
    //前0个物品，是否能够装满重量为1的背包，肯定可以  1 true 0 false
    dp[0][0] = 0;

    //init
    for (int i = 1; i <= w; i++) {
        dp[0][i] = 0;
    }

    for (int i = 1; i < nums.length; i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= nums.length; i++) {
        //前i个物品
        for (int j = 1; j <= w; j++) {
            //重量
            if (nums[i - 1] > j) {
                //自身的重量，比背包容量大，不能放进去了
                dp[i][j] = dp[i - 1][j];
            } else {
                //超出自身的重量，查看前i个数在这个重量上，最多放多少，直接加进去即可
                dp[i][j] = Math.max(dp[i - 1][j], nums[i - 1] + dp[i - 1][j - nums[i - 1]]);
            }
            Log.d(TAG, "backpack2: i = " + i + " j =" + j + " w=" + dp[i][j]);
        }
    }
    return dp[nums.length][w];
}

此后填充元素的原则，还是判断当前自身的重量是否能够装满背包，如果超出了背包的体积，那么就还是用上一行的最值；

如果没有超出背包的体积，那么从上一行查找剩余重量最多能装多少，然后与当前物品重量相加，这里需要注意一点，如上图第3行第3列，根据规则计算的值要比上一行小，因为要取最优解，因此需要取最大值。

2.1.2 带价值的01背包问题

有 n 个物品和一个大小为 m 的背包. 给定数组 nums 表示每个物品的大小和数组 values 表示每个物品的价值.

问最多能装入背包的总价值是多大?

那么这道题是带上了价值参数，要求价值最大，反而重量将不会是最重要的，因为重量最大不一定代表价值最大。

首先定义状态数组dp[i][j]，代表前i个物品，在容量不超过j的情况下最大价值，此时数组中每个位置的值将不再是重量之和，而是价值之和。

public static int backpack2(int[] nums, int[] v, int w) {

    //背包问题
    if (nums == null || nums.length == 0) {
        return 0;
    }

    //state

    //dp[i][j] 代表前i个物品最多能够装满重量为j的背包
    int[][] dp = new int[nums.length + 1][w + 1];
    //前0个物品，是否能够装满重量为1的背包，肯定可以  1 true 0 false
    dp[0][0] = 0;

    //init
    for (int i = 1; i <= w; i++) {
        dp[0][i] = 0;
    }

    for (int i = 1; i < nums.length; i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= nums.length; i++) {
        //前i个物品
        for (int j = 1; j <= w; j++) {
            //重量
            if (nums[i - 1] > j) {
                //自身的重量，比背包容量大，不能放进去了
                dp[i][j] = dp[i-1][j];
            } else {
                //超出自身的重量，查看前i个数在这个重量上，最多放多少，直接加进去即可
                dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - nums[i - 1]]);
            }
        }
    }
    return dp[nums.length][w];
}

2.2 多重背包问题

相较于01背包问题，多重背包问题对于每一个物品可以多选，所以针对此问题的策略也将会调整。

上述决策树中，我是按照背包中能装入最多物品来计算，例如第一个物品，重量为2，那么当背包容器大小为10时，那么可以放入5个1物品，因此dp[1][10]的最大价格就是1∗5=5 1 * 5 = 51∗5=5，因为物品的价格与质量不成正比，所以并不代表装入同一类型的物品越多，价值就越高。

因此在背包容量超出物品大小的时候，通过for循环来判断装入的个数为多少时，能得到最大的价值。

public static int backpack3(int[] nums, int[] v, int w) {

    //背包问题
    if (nums == null || nums.length == 0) {
        return 0;
    }

    //state

    //dp[i][j] 代表前i个物品最多能够装满重量为j的背包
    int[][] dp = new int[nums.length + 1][w + 1];
    dp[0][0] = 0;

    //init
    for (int i = 1; i <= w; i++) {
        dp[0][i] = 0;
    }

    for (int i = 1; i < nums.length; i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= nums.length; i++) {
        //前i个物品
        for (int j = 1; j <= w; j++) {
            //重量
            if (nums[i - 1] > j) {
                //自身的重量，比背包容量大，不能放进去了
                dp[i][j] = dp[i - 1][j];
            } else {
                //先看看能装几个
                int count = j / nums[i - 1];
                //看看取哪个count，能拿到最大值
                int maxVal = Integer.MIN_VALUE;
                for (int size = 1; size <= count; size++) {
                    int cur = Math.max(dp[i - 1][j], size * v[i - 1] + dp[i - 1][j - size * nums[i - 1]]);
                    if (cur > maxVal) {
                        maxVal = cur;
                    }
                }
                dp[i][j] = maxVal;
            }
        }
    }
    return dp[nums.length][w];
}

背包问题，主要分为01背包问题和多重背包问题，在解题思路上都是需要在二维数组上做文章，在定义状态数组dp[i][j]时，与坐标型的动态规划问题不同之处在于，j代表的是总数，而不是位置信息，例如背包的体积或者大小。

那么在处理01背包问题时，其实面对的抉择就是选或者不选，当物品的体积小于背包时，我们不能选择这个物品，此时我们拿上一行的最大值即可。当物品的体积大于背包时，我们考虑选择它，并与剩余空间的最优解累加，判断是否是最有解，通常与dp[i-1][j]比较。

而在处理多重背包问题时，因为每个物品有无数个，而且也可以选择任意个数加入到背包中，但是并不代表每个物品投入的多，就能得到最优解，因此我们通过for循环来控制变量获取最优解。