LeetCode题解——动态规划（四）

浅浅的花香味﹌ 2023-07-11 08:49 15阅读 0赞

### 文章目录 ###

*   *   *  474. 一和零
         *   *  动态规划
         *  322. 零钱兑换
         *   *  动态规划
         *  518. 零钱兑换 II
         *   *  动态规划
         *  139. 单词拆分
         *   *  动态规划
         *  377. 组合总和 Ⅳ
         *   *  动态规划
             *  推荐阅读

### 474. 一和零 ###

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

给定 0 和 1 的数量都不会超过 100。  
给定字符串数组的长度不会超过 600。  
示例 1:

输入: Array = \{“10”, “0001”, “111001”, “1”, “0”\}, m = 5, n = 3  
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 “10”,“0001”,“1”,“0” 。  
示例 2:

输入: Array = \{“10”, “0”, “1”\}, m = 1, n = 1  
输出: 2

解释: 你可以拼出 “10”，但之后就没有剩余数字了。更好的选择是拼出 “0” 和 “1” 。

#### 动态规划 ####

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。

class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
        
            if (strs == null || strs.length == 0) {
        
                return 0;
            }
            int[][] dp = new int[m + 1][n + 1];
            for (String s : strs) {
        
                int ones = 0, zeros = 0;
                for (char c : s.toCharArray()) {
        
                    if (c == '0') {
        
                        zeros++;
                    } else {
        
                        ones++;
                    }
                }
                for (int i = m; i >= zeros; i--) {
        
                    for (int j = n; j >= ones; j--) {
        
                        dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }

### 322. 零钱兑换 ###

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = \[1, 2, 5\], amount = 11  
输出: 3  
解释: 11 = 5 + 5 + 1  
示例 2:

输入: coins = \[2\], amount = 3  
输出: -1  
说明:  
你可以认为每种硬币的数量是无限的。

#### 动态规划 ####

因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。

class Solution {
        
        public int coinChange(int[] coins, int amount) {
        
            if (coins == null || coins.length == 0) {
        
                return -1;
            }
            if (amount == 0) {
        
                return 0;
            }
            int[] dp = new int[amount + 1];
            int coinMin = 0;
            for (int coin : coins) {
        
                for (int i = coin; i <= amount; ++i) {
        
                    if (i == coin) {
        
                        dp[i] = 1;
                    } else if (dp[i] == 0 && dp[i - coin] != 0) {
         
                        dp[i] = dp[i - coin] + 1;
                    } else if (dp[i - coin] != 0) {
        
                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    }
                }
                if (coin < coinMin) {
        
                    coinMin = coin;
                }
            }
            if (coinMin > amount) {
        
                return -1;
            }
            return dp[amount] == 0 ? -1 : dp[amount];
        }
    }

### 518. 零钱兑换 II ###

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = \[1, 2, 5\]  
输出: 4  
解释: 有四种方式可以凑成总金额:  
5=5  
5=2+2+1  
5=2+1+1+1  
5=1+1+1+1+1  
示例 2:

输入: amount = 3, coins = \[2\]  
输出: 0  
解释: 只用面额2的硬币不能凑成总金额3。  
示例 3:

输入: amount = 10, coins = \[10\]  
输出: 1

注意:

你可以假设：

0 <= amount (总金额) <= 5000  
1 <= coin (硬币面额) <= 5000  
硬币种类不超过 500 种  
结果符合 32 位符号整数

#### 动态规划 ####

完全背包问题，使用 dp 记录可达成目标的组合数目。

class Solution {
        
        public int change(int amount, int[] coins) {
        
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
        
            for (int i = coin; i <= amount; i++) {
         //将逆序遍历改为正序遍历
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
        }
    }

### 139. 单词拆分 ###

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。  
你可以假设字典中没有重复的单词。  
示例 1：

输入: s = “leetcode”, wordDict = \[“leet”, “code”\]  
输出: true  
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。  
示例 2：

输入: s = “applepenapple”, wordDict = \[“apple”, “pen”\]  
输出: true  
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。  
注意你可以重复使用字典中的单词。  
示例 3：

输入: s = “catsandog”, wordDict = \[“cats”, “dog”, “sand”, “and”, “cat”\]  
输出: false

#### 动态规划 ####

dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。

该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 “leetcode”：

["lee", "tc", "cod"]

求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。

class Solution {
        
        public boolean wordBreak(String s, List<String> wordDict) {
        
            int n = s.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            for (int i = 0; i <= n; i++) {
        
                for (String word : wordDict) {
        
                    int len = word.length();
                    if (len <= i && word.equals(s.substring(i - len, i))) {
        
                        dp[i] = dp[i] || dp[i - len];
                    }
                }
            }
            return dp[n];
        }
    }

### 377. 组合总和 Ⅳ ###

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = \[1, 2, 3\]  
target = 4

所有可能的组合为：  
(1, 1, 1, 1)  
(1, 1, 2)  
(1, 2, 1)  
(1, 3)  
(2, 1, 1)  
(2, 2)  
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。  
进阶：  
如果给定的数组中含有负数会怎么样？  
问题会产生什么变化？  
我们需要在题目中添加什么限制来允许负数的出现？

#### 动态规划 ####

有顺序限制的完全背包。

class Solution {
        
        public int combinationSum4(int[] nums, int target) {
        
            if (nums == null || nums.length == 0) {
        
                return 0;
            }
            int[] dp = new int[target + 1];
            dp[0] = 1;
            Arrays.sort(nums);
            int n = nums.length;
            for (int i = 1; i <= target; ++i) {
        
                for (int j = 0; j < n && nums[j] <= i; ++j) {
        
                    dp[i] += dp[i - nums[j]];
                }
            }
            return dp[target];
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GaGwyRXlvT0hyTldRcjhHSE9fdUE3d2JYNFpI?x-oss-process=image/format,png