重启DAY13 0-1背包完全背包

跟着灵茶山艾府大佬学习算法思路的day13（并没有在一个月内掌握hot100）

b站链接如下：

既然动态规划的递归可以优化为递推，为什么回溯问题不将递归改换为递推？

回溯本质就是递归，当然能转递推。但大多数回溯题没必要，因为回溯要的是所有方案本身，不是方案数或最优值。回溯求的是具体方案（每条路径都要输出），DP 求的是数值结果（方案数或最优值）。回溯要保留完整路径，每一步都得存着，没法丢弃中间状态，所以递推的优化手段（备忘录跳过、滚动变量覆盖）都用不上，空间省不了，写起来还更复杂，不如递归自然。

0-1背包和完全背包都是非常重要的DP模型，可以说它们就是选或不选这个思想的代表。

目标和题目描述：

给你一个非负整数数组 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

思路：

对于0-1背包问题，和打家劫舍思路类似，但会显式地传递一个容量限制（二维dp），而打家劫舍的限制比较简单，隐式地藏在数组下标中（一维dp）。

如果用代码实现0-1背包的递归会如下，注意使用的记忆数组需要是二维的，同时记录物品号数和剩余容量。

目前本题和0-1背包的关系还不够明显，最直观的思路似乎是构建每个元素选择-号或+号的二叉决策树，这样直接就可以开始递归，这种情况下显然时间复杂度为o(n)。然后也可以发现具有部分子问题的重复，从而可以应用备忘录，但应用后应该就能发现，只能将时间复杂度降低到O(n × sum)，因为状态是(i, sum)两个维度。

如果按照二叉决策+备忘录的思路，其实已经可以通过判题，但其实仍旧是打家劫舍的选或不选思路，而背包问题才是这道题隐藏的新内容。

可以通过数学推导（这个推导并不容易发现），将原问题转化为一个0-1背包问题。

p为需要添加正号的数的数值和，s为nums数组的元素和，s-p为需要添加负号的数的数值和，用t标记target，t = p - (s - p)，再次化简后可以得到p = (s + t) / 2。那么问题就变成了在nums中选择一些数字，使得他们的和恰好为(s + t) / 2的方案数。

由此推论可知，s + t必须是偶数，且根据题目提示的s和t的范围，s+t也不可能为负数。

如此转换后，这题就变为求解选一些数，使得这些数之和恰好为某一个数的方案数了，这是0-1背包的一种常见变形。

然后就可以通过0-1背包的递归思路来完成，并逐步进行到空间优化。

代码：

二叉决策+备忘录（这个思路已经可以通过判题，但和0-1背包思路有本质区别）：

  
var findTargetSumWays = function(nums, target) {
    const n = nums.length;
    const memo = new Map();

    const dfs = (i, sum) => {
        if (i === n) {
            return sum === target ? 1 : 0;
        }

        const key = i + ',' + sum;
        if (memo.has(key)) return memo.get(key);

        const res = dfs(i + 1, sum + nums[i]) // 选 +
        + dfs(i + 1, sum - nums[i]); // 选 -

        memo.set(key, res); // 限制为2维，使用映射
        return res;
    };

    return dfs(0, 0);
};

二叉决策的递推版（不太值得写，相较于0-1背包状态太大了），二叉决策的 sum 范围是 -total ~ total，要开 (n + 1) × (2 × total + 1) 的数组：

  
var findTargetSumWays = function(nums, target) {
    const n = nums.length;
    const total = nums.reduce((a, b) => a + b, 0);

    // sum 范围 [-total, total]，下标偏移 total 映射到 [0, 2*total]
    const offset = total;
    const f = Array.from({ length: n + 1 }, () => new Array(2 * total + 1).fill(0));
    f[0][offset] = 1; // 初始 sum = 0，对应下标 total

    for (let i = 0; i < n; i++) {
    	for (let s = -total; s <= total; s++) {
            if (f[i][s + offset] === 0) continue; // 跳过不可能的状态
            f[i + 1][s + nums[i] + offset] += f[i][s + offset]; // 选 +
            f[i + 1][s - nums[i] + offset] += f[i][s + offset]; // 选 -
        }
    }

    return f[n][target + offset];
};

0-1背包的递归：

  
var findTargetSumWays = function(nums, target) {
    const s = nums.reduce((a, b) => a + b, 0) - Math.abs(target);
    if (s < 0 || s % 2 !== 0) return 0;
    const m = s / 2; // 背包容量

    const memo = new Map();

    const dfs = (i, c) => {
        if (i < 0) {
            return c === 0 ? 1 : 0;
        }
        const key = i + ',' + c;
        if (memo.has(key)) return memo.get(key);

        let res;
        if (c < nums[i]) {
            res = dfs(i - 1, c); // 只能不选
        } else {
            res = dfs(i - 1, c) + dfs(i - 1, c - nums[i]); // 不选 + 选
        }

        memo.set(key, res);
        return res;
    };

    return dfs(nums.length - 1, m);
};

1:1翻译成递推：

  
var findTargetSumWays = function(nums, target) {
    const s = nums.reduce((a, b) => a + b, 0) - Math.abs(target);
    if (s < 0 || s % 2 !== 0) return 0;
    const m = s / 2;
    const n = nums.length;

    const f = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
    // 行号代表目前到达的数字，列号代表容量，容量可取的值范围为0-m
    f[0][0] = 1;

    for (let i = 0; i < n; i++) {
        const x = nums[i];
        for (let c = 0; c <= m; c++) {
            if (c < x) {
                f[i + 1][c] = f[i][c];
            } else {
                f[i + 1][c] = f[i][c] + f[i][c - x];
            }
        }
    }

    return f[n][m];
};

两个数组的滚动数组：

用两行数组交替覆盖，i % 2和 (i + 1) % 2在 0 和 1 之间来回切换，空间从 O(n × m) 降到 O(2 × m)。

  
var findTargetSumWays = function(nums, target) {
    const s = nums.reduce((a, b) => a + b, 0) - Math.abs(target);
    // s即为推导中的(s + t)
    // 即使取绝对值，方案最后的总数量也是不变的，只是每个方案的正负号会和原来相反
    if (s < 0 || s % 2 !== 0) return 0;
    const m = s / 2; // 背包容量，(s + t) / 2
    const n = nums.length;

    const f = Array.from({ length: 2 }, () => new Array(m + 1).fill(0));
    f[0][0] = 1;

    for (let i = 0; i < n; i++) {
        const x = nums[i];
        for (let c = 0; c <= m; c++) {
            if (c < x) {
                f[(i + 1) % 2][c] = f[i % 2][c];
            } else {
                f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - x];
            }
        }
    }

    return f[n % 2][m];
};

由于f[c]的当前取值依赖的是上一个数组中对应位置在c之前和在c所在位置的数值，所以如果从后面开始更新数组，可以只用一个数组：

  
var findTargetSumWays = function(nums, target) {
    const s = nums.reduce((a, b) => a + b, 0) - Math.abs(target);
    if (s < 0 || s % 2 !== 0) return 0;
    const m = s / 2;

    const f = new Array(m + 1).fill(0);
    f[0] = 1;

    for (const x of nums) {
        for (let c = m; c >= x; c--) { // 倒序
        	f[c] = f[c] + f[c - x];
        }
    }

    return f[m];
};

总结：

这题可以用打家劫舍的思路解决，但更重要的是要了解将本题转化为0-1背包问题的思路，以及掌握0-1背包问题。如果使用最直接的二叉决策思路，状态会比较多，记忆化搜索相对没有那么优雅。

此外，滚动变量是递推的独特优势之一，递归是无法实现的，因为无法知道当前结果什么时候被最后一层用到，没法确定什么时候能安全覆盖。当然，这也是一步一步来的，先写出递归，再改写为递推，最后再看看有没有节省空间的可能。

零钱兑换问题描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路：

每种物品都可以重复选，就是0-1背包问题的变种，完全背包问题。完全背包问题在不选时是和0-1一样的，但如果选择i，因为可以重复选，就不是递归到i-1了，而是需要仍然递归到i，只变化容量，不变化物品序号。

从这一点而言，只需要把0-1背包问题中的选中i-1改为i，就是完全背包问题最简单的代码框架。

而对于零钱兑换这一题，是完全背包问题的变体，是恰好装够容量，求方案的最小价值和。因为背包问题的容量是固定的，价值是变化的，而这里的总金额也是固定的，硬币个数是变动的；那么可以将金额视为容量，硬币个数视为价值，每个硬币对应价值定义为1，这样只需将求最大改为求最小，就吻合了题目要求最少硬币个数的要求。

按照类似的思路，可以把递归加记忆化搜索完成，递推和滚动数组也是类似的思路。如果要用一个数组，和上一题正好相反，从头开始正序遍历就是对的。因为和0-1背包问题相比，0-1背包两个数都是从旧数组取（f[c] = f[c](旧) + f[c-x](旧)），完全背包一个数是旧数组、一个数是新数组（f[c] = f[c](旧) + f[c-x](新)）。最后的空间复杂度会被优化到o(amount)。

代码：

递归版本（超出时间限制）：

  
var coinChange = function(coins, amount) {
    const n = coins.length; // 有多少种物品

    const dfs = (i, c) => {
        if (i < 0) { // 考虑完所有种物品时
            return c === 0 ? 0 : Infinity;
            // 因为需要正好凑够amount，所以只有c为0时才能返回0
        }

        if (c < coins[i]) { // 硬币的面额已经大于目前还剩的面额
            return dfs(i - 1, c);
        }

        return Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        // 选了还能接着选
    }

    ans = dfs(n - 1, amount);
    return ans < Infinity ? ans : -1;
};

递归+记忆化：

  
var coinChange = function(coins, amount) {
    const n = coins.length; // 有多少种物品
    const memo = Array.from({ length : n }, () => new Array(amount + 1).fill(-1));
    // 完全背包的可重复选不会影响记忆化的复杂度
    // 因为dfs过程已经保证了到达当前物体时的当前剩余容量和目前价值和的一比一映射关系

    const dfs = (i, c) => {
        if (i < 0) { // 考虑完所有种物品时
            return c === 0 ? 0 : Infinity;
            // 因为需要正好凑够amount，所以只有c为0时才能返回0
        }

        if (memo[i][c] !== -1) {
            return memo[i][c];
        }

        let res; // 暂存值，用以更新memo

        if (c < coins[i]) {
            res = dfs(i - 1, c);
        } else {
            res = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        }

        memo[i][c] = res;
        return res;

    }

    ans = dfs(n - 1, amount);
    return ans < Infinity ? ans : -1;
};

1:1改写递推：

  
var coinChange = function(coins, amount) {
    const n = coins.length;
    const INF = Infinity;

    // 第1步：参数 (i, c) → dp[i+1][c]，下标偏移1，因为 i<0 对应第0行
    const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(INF));

    // 第2步：base case → 初始值
    // i < 0 && c === 0 → return 0
    dp[0][0] = 0;

    // 第3步：转移方程照抄，dfs(i-1, c) → dp[i][c]，dfs(i, c-x) → dp[i+1][c-x]
    for (let i = 0; i < n; i++) {
        const x = coins[i];
        for (let c = 0; c <= amount; c++) {
            if (c < x) {
            	dp[i + 1][c] = dp[i][c]; // 只能不选
            } else {
            	dp[i + 1][c] = Math.min(dp[i][c], dp[i + 1][c - x] + 1); // 不选与继续选
            }
        }
    }

    return dp[n][amount] < INF ? dp[n][amount] : -1;
};

使用滚动数组：

  
var coinChange = function(coins, amount) {
const n = coins.length;
const INF = Infinity;

// 只留两行，交替使用
const dp = Array.from({ length: 2 }, () => new Array(amount + 1).fill(INF));
dp[0][0] = 0;

for (let i = 0; i < n; i++) {
    const x = coins[i];
    for (let c = 0; c <= amount; c++) {
        if (c < x) {
        	dp[(i + 1) % 2][c] = dp[i % 2][c];
        } else {
        	dp[(i + 1) % 2][c] = Math.min(dp[i % 2][c], dp[(i + 1) % 2][c - x] + 1);
        }
    }
}

return dp[n % 2][amount] < INF ? dp[n % 2][amount] : -1;
};

最终优化为单数组：

  
var coinChange = function(coins, amount) {
    const INF = Infinity;
    const dp = new Array(amount + 1).fill(INF);
    dp[0] = 0;

    for (const x of coins) {
        for (let c = x; c <= amount; c++) { // 完全背包的正序遍历
        	dp[c] = Math.min(dp[c], dp[c - x] + 1);
        }
    }

    return dp[amount] < INF ? dp[amount] : -1;
};

总结：

主要的难点在于将问题转化为背包问题，和区分0-1背包和完全背包的特性。

重启DAY13 0-1背包 完全背包

目标和 题目描述：

思路：

代码：

总结：

零钱兑换 问题描述：

思路：

代码：

总结：

相关文章

重启DAY17 区间 DP：最长回文子序列

重启DAY12 动态规划入门：从记忆化搜索到递推

重启DAY14 线性DP 最长公共子序列 编辑距离

重启DAY13 0-1背包完全背包

目标和题目描述：

零钱兑换问题描述：

重启DAY14 线性DP 最长公共子序列编辑距离