[数据结构与算法]动态规划之如何将问题抽象转化为0-1背包问题（详解利用动态规划求方案数）

??前面的话??

本篇文章介绍如何对问题抽象转化成0-1背包问题求解和运用0-1背包求方案数。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年5月11日🌴
??坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《漫画算法》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

??如何将问题抽象为0-1背包??

通过一道题来说明如何将问题抽象为0-1背包问题。

🔐最后一块石头的重量 II

题目：1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

💡解题思路

分析：

题目告诉了我们每个石头的重量，两块石头粉碎后，只会剩下正差值的重量的石头，该石头可能会再次参与粉碎操作，题目要求的是一堆石头经过很多次两两粉碎后，剩余最后一块的 最小 重量。

两块石头进行“粉碎时”可以将重量较大的石头分为一组，称为大堆，粉碎时，相当于给大堆的石块赋予+权重，将重量较小的石头分为一组，称为小堆，给小堆的石块赋予-权重，当我们不考虑粉碎后的石头放回的情况时，本质上就是计算赋予+或-得到的计算式子的值。

如果考虑粉碎石头重新放回的情况，其实本质上就是将原来分好的石块进行重组，比如假如有两个石块重量分别为a, b，满足a>=b，则粉碎后新石头的重量为a-b，不妨将这块新得到的石头称为“粉碎重生石”，该石头遇到一个比自身重量大的石头，重量为c，再次粉碎后，重量为c-(a-b)，我们发现相比于原来的式子，只是a的权重变为-，b的权重变为+，也就是发生了两个石头的权重发生了交换，同理，“粉碎重生石”遇到比自身重量小的石头，重量为d，则粉碎后重量变为(a-b)-d，a，b的权重不改变。虽然a,b的权重发生了改变，即对于大堆里面的单块石头不一定会比小堆里面的单块石头重，但是大堆的重量和依然会大于小堆的重量和。由于大堆里面的石头重量权重全部是+，小堆里面的石头权重全部为-，所以不妨将大堆称为+权重堆，小堆称为-权重堆。

综上分析，石头经历多次粉碎，改变的仅仅只是分布在哪一个组里面而已，只不过组的分界条件，由两块石头哪块更重变为最终石头被赋予的权重是+还是-，所以本质上就是给石堆重量数组中的元素添加+/-号，得到一个计算表达式，然后去求这个表达式的值，满足最接近0并不小于0的那个表达式的值就是我们所要的答案，也就是最后一块石头的重量。

那么此时，问题不知不觉就转化为：给你一堆石头的重量，每个石头只能选择一次，每次你可以加这个石头的重量，也可以减石头的重量，求不小于0的最小重量。

那这不就和之前做的[分割等和子集]那道题很像吗？我们把被赋予+权重的石头分为一组，被赋予-权重的石头分为一组，这两组就相当于数组的两个子集，求两个子集的最小差值。

不妨设+权重堆的总重量为big_sum，不妨设-权重堆的总重量为small_sum，那差值重量就是big_sum-small_sum的绝对值。假设石堆的总重量为sum，则sum=big_sum+small_sum，经过上述分析big_sum>=small_sum。

不难推出small_sum<=sum/2，即此时问题变为从石堆重量数组中选择若干元素，求不超过sum/2的最大元素和，这就完完全全的0-1背包问题了。

最后再拿这个最大和的两倍减去sum得到的就是最后一块石头的重量。

状态定义：

$dp[i][j]$表示从前$i$个元素中选择，不超过$j$的最大元素和，其中每个元素只能选择一次。

确定初始状态：

我们考虑当$i=0$时表示没有任何元素可以选择，所以不论$j$为何值时，$dp[i][j]=0$。

状态转移方程：

我们考虑选择第$i$个元素，重量为$stones[i?1]$，如果我们不选择该元素，$dp[i][j]=dp[i?1][j]$，如果我们选择该元素，前提必须满足$j>=stones[i?1]$，此时$dp[i][j]=dp[i?1][j?stones[i?1]]$，由于是求最大值，所以选择两者更大的那一个。

所以最终状态转移方程为$dp[i][j]=max(dp[i?1][j],dp[i?1][j?stones[i?1]])$。

实现代码：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int x : stones) {
            sum += x;
        }
        int ret = sum / 2;
        int n = stones.length;
        int[][] dp = new int[n+1][ret+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= ret; j++) {
                int x = dp[i-1][j];
                int y = j >= stones[i-1] ? dp[i-1][j-stones[i-1]] + stones[i-1] : 0;
                dp[i][j] = Math.max(x, y);
            }
        }
        return sum - 2 * dp[n][ret];
    }
}

时间复杂度：$O(n?sum/2)$
空间复杂度：$O((n+1)?(sum/2+1))$

滚动数组优化：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int x : stones) {
            sum += x;
        }
        int ret = sum / 2;
        int n = stones.length;
        int[][] dp = new int[2][ret+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= ret; j++) {
                int index = (i-1) & 1;
                int x = dp[index][j];
                int y = j >= stones[i-1] ? dp[index][j-stones[i-1]] + stones[i-1] : 0;
                dp[i&1][j] = Math.max(x, y);
            }
        }
        return sum - 2 * dp[n&1][ret];
    }
}

时间复杂度：$O(n?sum/2)$
空间复杂度：$O(2?(sum/2+1))$
一维数组优化：
$dp[j]$仅依赖上一行的$dp[j]$与$dp[j?stones[i?1]]$，更新第$j$列的值时$j?stones[i?1]$列的值必须还是未更新的值，所以采取从后往前遍历的方式，为了保证$j>=stones[i?1]$，$j$的最小取值为$stones[i?1]$。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int x : stones) {
            sum += x;
        }
        int ret = sum / 2;
        int n = stones.length;
        int[] dp = new int[ret+1];
        for (int i = 1; i <= n; i++) {
            for (int j = ret; j >= stones[i-1]; j--) {
                int x = stones[i-1];
                dp[j] = Math.max(dp[j], dp[j-x]+x);
            }
        }
        return sum - 2 * dp[ret];
    }
}

时间复杂度：$O(n?(sum/2?stones[i?1]))$
空间复杂度：$O(sum/2+1)$

📝练习：目标和

题目： 494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

🔑习题解答

分析：

这道题就是给数组nums的元素添加+/-权重，使得计算式的值为target，与上面【最后一块石头的重量 II】的区别就是前者求计算式结果不小于0的最小值，这里是求计算式的结果为target的方案数，本质上还是一共0-背包问题，只不过价值与物品空间的对应关系发生了改变而已，即每个物品的价值均为1。

我们先来考虑计算式的极限边界，不妨设数组nums的元素绝对值的和为s，当权重全部为-时，计算式的结果为-s，当权重全部为+时，计算式结果为s，所以计算式的范围是$[?s,s]$区间内的整数，一共$2?s+1$个。

然后我们来考虑定义状态的定义。

状态定义：
定义$dp[i][j]$为前$i$个元素加权后构成计算式的值为$j$的方案数，$?s<=j<=s$。

我们知道计算式的范围是$[?s,s]$区间内的整数，由于数组的下标不能为负值，所以我们定义动态规划数组时需向右偏移$s$位，即$dp[i][0]$中的目标值$j=?s$，那么$dp[i][s]$中的目标值为$j=0$，不难推出实际下标值为$j+s$。计算式的范围有$2s+1$个整数，所以需要申请动态规划数组的列数为$2?s+1$。

确定初始状态：

当没有元素可以加权时，它的结果只能是0，所以只有当j为0时有一种方案，其余情况均没有方案，我们考虑这种情况为初始状态，则$dp[0][s]=1$，$j>=1$时$dp[0][j+s]=0$。

状态转移方程：

所谓对数组元素加权+/-其实就是决定该元素是被加还是被减，我们来考虑第i个元素，假设该元素的值为t，如果选择加，则方案数为$dp[i?1][j+s?t]$，前提是$j+s?t>=0$，如果选择减，则方案数为$dp[i?1][j+s+t]$，前提是$j+s+t<=2?s$。此时的方案数为满足上述两种情况方案数之和，如果$j+s?t<0$或$j+s+t>2?s$，则对应的方案数就是$0$。

状态转移方程为$dp[i][j]=dp[i?1][j+s?t]+d[i?1][j+s+t]$。

实现代码：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划
        //状态转移方程dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
        //i表示数组前i个元素，j表示目标和，dp[i][j]表示从前i个元素中进行+/-得到j的方案数
        //考虑极端情况，目标和最大取值为数组的元素绝对值之和记为s，最小值为-s,所以j的可能取值一共2s+1个

        //1. 求数组元素绝对值的和
        int s = 0;
        for (int x : nums) {
            s += Math.abs(x);
        }
        //如果target绝对值大于数组目标和的最大值，不可能存在合法的方案
        if (Math.abs(target) > s) {
            return 0;
        }
        //2. 创建动态规划数组
        int len = nums.length;
        int[][] dp = new int[len + 1][2 *s + 1];

        //3. 初始化,0->-s,s->0
        dp[0][s] = 1;

        //4. 处理剩余情况
        for (int i = 1; i <= len; i++) {
            int t = nums[i - 1];
            for (int j = -s; j <= s; j++) {
                //当权重为+时，如果满足合法范围,加上dp[i - 1][j + s - t]
                if (j + s - t >= 0) {
                    dp[i][j + s] += dp[i - 1][j + s - t];
                }
                //当权重为-时，如果满足合法范围,加上dp[i - 1][j + s + t]
                if (j + s + t <= 2 * s) {
                    dp[i][j + s] += dp[i - 1][j + s + t];
                }
            }
        }
        return dp[len][target+s];
    }
}

时间复杂度：$O(2?len?s)$
空间复杂度：$O(2?len?s)$

滚动数组优化：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划
        //状态转移方程dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
        //i表示数组前i个元素，j表示目标和，dp[i][j]表示从前i个元素中进行+/-得到j的方案数
        //考虑极端情况，目标和最大取值为数组的元素绝对值之和记为s，最小值为-s,所以j的可能取值一共2s+1个

        //1. 求数组元素绝对值的和
        int s = 0;
        for (int x : nums) {
            s += Math.abs(x);
        }
        //如果target绝对值大于数组目标和的最大值，不可能存在合法的方案
        if (Math.abs(target) > s) {
            return 0;
        }
        //2. 创建动态规划数组
        int len = nums.length;
        int[][] dp = new int[2][2 *s + 1];

        //3. 初始化,0->-s,s->0
        dp[0][s] = 1;

        //4. 处理剩余情况
        for (int i = 1; i <= len; i++) {
            int t = nums[i - 1];
            for (int j = -s; j <= s; j++) {
                //更新值时，需要对原来那一行的值归零
                dp[i&1][j + s] = 0;                
                //如果满足左边界的值,加上dp[i - 1][j + s - t]
                if (j + s - t >= 0) {
                    dp[i&1][j + s] += dp[(i-1)&1][j + s - t];
                }
                //如果满足右边界的值，加上dp[i - 1][j + s + t]
                if (j + s + t <= 2 * s) {
                    dp[i&1][j + s] += dp[(i-1)&1][j + s + t];
                }
            }
        }
        return dp[len&1][target+s];
    }
}

时间复杂度：$O(2?len?s)$
空间复杂度：$O(4?s)$

由于当行的数据更新，与前一行的前后都有关系，因此对于这道题不适合一维优化，但是我们定义状态时，考虑了$[?s,s]$区间内所有的值，这就包含了目标情况不可能取到的一些状态值。下面我们根据这一点来进行优化。

?优化方案

比如当题目给的$target$不为$s$和$?s$时，那这两个值就是无效的状态值。为了规避掉这些无效的状态值，我们重新开始再来分析分析，我们将赋予$+$权重的分为一组叫做【正权重部分】,反之将赋予$?$的分为一组叫做【负权重部分】，不妨设数组的绝对值元素和为$s$，【负权重部分】的绝对值元素和为$m$，则【正权重部分】的元素和为$s?m$，我们可以做以下的推导。
由题意得到，目标值$target$为【正权重部分】的计算值减去【负权重部分】的计算值（绝对值）。
$$(s?m)?m=target$$
$$s?2?m=target$$
$$m=\frac{s?target}{2}$$

根据推断，只要凑出$m$，那么【正权重部分】也就确定了，于是问题就变成仅使用$+$，从数组中凑出$m$的方案数，但是前提是$s?target$能够被$2$整除，如果不能被$2$整除，表示无法凑出$target$，方案数直接为$0$，所以需要在$s?target$为偶数的情况下，才会存在有效的方案。

在原问题中的$m$会被赋予负权重，剩下的元素会被赋予正权重，由以上分析我们可以开始定义状态。

状态定义：
$dp[i][j]$表示从数组前$i$个元素中选择（每个元素只能被选择一次）,凑出的元素和恰好为$j$的方案数。
确定初始状态：
当没有任何元素可以选择时，显然除了$dp[0][0]=1$其余的均没有方案。
状态转移方程：
对于第$i$个元素，值为$t$，如果不选，则方案数为$dp[i?1][j]$，如果选择，则方案数$dp[i?1][j?t]$，总方案数$dp[i][j]=dp[i?1][j]+dp[i?1][j?t]$。

实现代码：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划
        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。

        //1. 求数组元素绝对值的和
        int s = 0;
        for (int x : nums) {
            s += Math.abs(x);
        }
        int m = (s - target) / 2;
        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案
        if (Math.abs(target) > s || (s - target) % 2 != 0) {
            return 0;
        }
        //2. 创建动态规划数组,一维优化
        int len = nums.length;
        int[][] dp = new int[len+1][m+1];

        //3. 初始化dp[0][0] = 1;
        dp[0][0] = 1;

        //4. 处理剩余情况
        for (int i = 1; i <= len; i++) {
            int t = nums[i - 1];
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= t) {
                    dp[i][j] += dp[i-1][j-t];
                }
            }
        }
        return dp[len][m];
    }
}

时间复杂度：$O(len?(s?target))$
空间复杂度：$O(len?(s?target))$

滚动数组优化：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划
        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。

        //1. 求数组元素绝对值的和
        int s = 0;
        for (int x : nums) {
            s += Math.abs(x);
        }
        int m = (s - target) / 2;
        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案
        if (Math.abs(target) > s || (s - target) % 2 != 0) {
            return 0;
        }
        //2. 创建动态规划数组,一维优化
        int len = nums.length;
        int[][] dp = new int[2][m+1];

        //3. 初始化dp[0][0] = 1;
        dp[0][0] = 1;

        //4. 处理剩余情况
        for (int i = 1; i <= len; i++) {
            int t = nums[i - 1];
            for (int j = 0; j <= m; j++) {
                dp[i&1][j] = dp[(i-1)&1][j];
                if (j >= t) {
                    dp[i&1][j] += dp[(i-1)&1][j-t];
                }
            }
        }
        return dp[len&1][m];
    }
}

时间复杂度：$O(len?(s?target))$
空间复杂度：$O(2?(s?target))$
一维数组优化：
我们根据状态转移方程可以发现当行的$dp[j]$只与前一行$dp[j]$与$dp[j?t]$有关，所以$dp[j]$更新要比$dp[j?t]$在前，且$j>j?t$，所以一维优化时需从后往前遍历，$j$最小取值为$t$，保证$j>=t$。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //动态规划
        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。

        //1. 求数组元素绝对值的和
        int s = 0;
        for (int x : nums) {
            s += Math.abs(x);
        }
        int m = (s - target) / 2;
        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案
        if (Math.abs(target) > s || (s - target) % 2 != 0) {
            return 0;
        }
        //2. 创建动态规划数组,一维优化
        int len = nums.length;
        int[] dp = new int[m+1];

        //3. 初始化dp[0] = 1;
        dp[0] = 1;

        //4. 处理剩余情况
        for (int i = 1; i <= len; i++) {
            int t = nums[i - 1];
            for (int j = m; j >= t; j--) {
                dp[j] += dp[j-t];
            }
        }
        return dp[m];
    }
}

时间复杂度：$O(len?(s?target?nums[i?1]))$
空间复杂度：$O(s?target)$

🌱参考资料：

宫水三叶背包问题

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖