算法训练营day39 | {322. 零钱兑换, 279.完全平方数, 139.单词拆分, 4.多重背包}

第九章动态规划part06，背包问题结束，继续动态规划吧~

322. 零钱兑换

题目链接：322. 零钱兑换
文档讲解：代码随想录
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换
状态：完全背包。

1.1 解题分析

题目描述：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

DP五部曲：

dp[j]数组定义：容量为j的背包最少需要dp[j]个硬币装满。
递推公式：
- dp[j] = min(dp[j], dp[j - coins[i]] + 1)
dp数组初始化：
- 容量为0，需要0个硬币 dp[0] = 0
遍历顺序：均可
打印dp数组。

1.2 解题小结

注意，加一个判断，当dp[j - coins[i]]能凑到时，再+1，否则不进行递推，以防止int溢出。

▶

322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

279. 完全平方数

题目链接：279.完全平方数
文档讲解：代码随想录
状态：和上一题的思路一样，比较简单。

2.1 解题分析

题目描述：给你一个整数n，返回和为n的完全平方数的最少数量。

DP五部曲：

dp[j]数组定义：容量为j的背包最少需要dp[j]个完全平方数装满。
递推公式：
- dp[j] = min(dp[j], dp[j - nums[i] * nums[i]] + 1)
dp数组初始化：
- 容量为0，需要0个完全平方数 dp[0] = 0
- 其他初始化为最大值。
遍历顺序：均可
打印dp数组。

▶

279. 完全平方数

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            int num = i * i;
            for (int j = num; j <= n; j++) {
                if (dp[j - num] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - num] + 1);
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}

139. 单词拆分

题目链接：139.单词拆分
文档讲解：代码随想录
视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分
状态：先想明白回溯暴力搜索，再来用完全背包解题，回溯比较简单。

3.1 回溯搜索

看成是一个切割字符串的问题，给定一个字符串s，能否切割成子串使得子串列表等于字符串列表wordDict。而切割字符串又能被抽象成一个组合问题。

回溯算法三部曲：

参数和返回值： 字符串s，子串列表wordDict，int型变量startIndex，用于记录本层for循环的起始下标。
递归终止条件： 如果已经到达字符串的末尾，则说明有一个可行解，返回true结果，终止递归。
单层递归逻辑：

从当前位置开始，尝试截取不同长度的前缀，如果这个前缀在字典中存在，就递归处理剩下的子串；如果剩下的子串也能被成功拆分，继续向上返回true。
如果当前前缀匹配失败，就尝试下一个可能的前缀。（剪枝）

以上暴力搜索会超时，原因是递归包含很多重复计算，需要增加一个记忆数组memo，记录每个start是否曾经被计算过。

▶

139. 单词拆分

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Boolean[] memo = new Boolean[s.length()];
        return backtracking(s, wordSet, 0, memo);
    }

    private boolean backtracking(String s, Set<String> wordSet, int startIndex, Boolean[] memo) {
        if (startIndex == s.length()) {
            return true;
        }

        if (memo[startIndex] != null) {
            return memo[startIndex];
        }

        for (int end = startIndex + 1; end <= s.length(); end++) {
            String subStr = s.substring(startIndex, end);
            if (!wordSet.contains(subStr)) continue;
            if (backtracking(s, wordSet, end, memo)) {
                memo[startIndex] = true;
                return true;
            }
        }
        memo[startIndex] = false;
        return false;
    }
}

3.2 完全背包

把字符串列表当作物品，字符串s当作背包，那么本题就是完全背包，dp[j]的含义是长度为j的字符串能够由wordSet中的物品组成，则为true，否则设为false。求dp[s.size()]是否为true。

DP五部曲：

dp[j]数组定义：首先值是bool型的，长度为j的字符串是否能由wordSet中的单词组成。
递推公式：
- 如果(i,j]这个区间的子串出现在wordSet中，并且dp[i]为true，则dp[j]为true
dp数组初始化：
- 全部初始化为false；除了空字符串dp[0] = true
遍历顺序：本题对子串有顺序要求，是排列数。
打印dp数组。

▶

139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        return knapsack(s, wordSet);
    }

    private boolean knapsack(String s, Set<String> wordSet) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int j = 1; j <= s.length(); j++) {
            for (int i = 0; i < j; i++) {
                String subStr = s.substring(i, j);
                if (wordSet.contains(subStr) && dp[i]) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}