代码随想录算法训练营第三十七天-322零钱兑换、279完全平方数、139单词拆分

前言
状态：322 递推公式看了题解。279 与 322 一样，AC 了。139 用回溯超时。
更新

1	24-06-25 初始记录

初步题解

322 零钱兑换

题目链接：(https://leetcode.cn/problems/coin-change)

确定 dp[i] 的含义：填满 i（包括 i）这么大容积的包，需要的最小个数为 dp[i]
递推公式：dp[i] = Math.min(dp[i], dp[i - coin] + 1)。（这里比较难想，背包放这个硬币的计算为不放的结果加一）
dp 数组的初始化：dp[0] = 0。背包大小为 0，方法数也为 0。（根据题中给出的示例 3）
遍历顺序：从前向后遍历（完全背包）。
打印 dp 数组（用于 debug）

/**  
 * 思路：  
 * 1. 硬币获取可以重复（完全背包）  
 * @param coins 硬币数组  
 * @param amount 数量  
 * @return 结果  
 */  
public static int coinChange(int[] coins, int amount) {  
    // dp 表示凑成金额所需要的最小个数  
    int[] dp = new int[amount + 1];  
    Arrays.fill(dp, amount + 1);  
  
    dp[0] = 0;  
  
    for (int coin : coins) {  
        for (int i = coin; i < dp.length; i++) {  
            if(dp[i - coin] != amount + 1) {  
                dp[i] = Math.min(dp[i], dp[i- coin] + 1);  
            }  
         }  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[amount] == amount + 1 ? -1 : dp[amount];  
}

279 完全平方数

题目链接：(https://leetcode.cn/problems/perfect-squares)

和上题完全一样，区别只有取值数组的值需要自己计算。

/**  
 * 思路：背包大小为n，从1-根号n之间取数  
 * 1. 数可以重复取值，完全背包  
 *  
 * @param n 和为n  
 * @return 结果  
 */  
public int numSquares(int n) {  
    // dp[i] 表示和为n的完全平方数的最小数量  
    int[] dp = new int[n + 1];  
    Arrays.fill(dp, n + 1);  
  
    dp[0] = 0;  
    int num = (int) Math.sqrt(n);  
    for (int i = 1; i <= num; i++) {  
        for (int j = i * i; j < dp.length; j++) {  
            if (dp[j - i * i] != n + 1) {  
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);  
            }  
        }  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[n];  
}

139 单词拆分

题目链接：(https://leetcode.cn/problems/word-break)

// 回溯方法。这样写会超时🤕
public boolean wordBreak(String s, List<String> wordDict) {  
    wordDict.sort(Comparator.comparingInt(String::length));  
    return wordBreakBFS(s, wordDict, new ArrayList<>());  
}  
  
public static boolean wordBreakBFS(String s, List<String> wordDict, List<String> word) {  
    String join = String.join("", word);  
    if (s.length() <= join.length()) {  
        return s.equals(String.join("", word));  
    } else if (!s.startsWith(join)) {  
        return false;  
    }  
  
    for (String string : wordDict) {  
        word.add(string);  
        boolean b = wordBreakBFS(s, wordDict, word);  
        if (b) {  
            return true;  
        }  
        word.remove(word.size() - 1);  
    }  
  
    return false;  
}

看解析

确定 dp[i] 的含义：字符串长度为 i，dp[i] 表示是否可以拆分，可以返回 true。
递推公式：如果 dp[j] 为 true，并且字符串下标 j-i 截取的字符在字典内，说明可以拆分。
dp 数组的初始化：dp[0] = true。初始值为了保证后续计算不会一直为 false。
遍历顺序：从前向后遍历（完全背包）。由于是排列问题，所以先遍历背包大小。
打印 dp 数组（用于 debug）

// 动态规划
public static boolean wordBreak(String s, List<String> wordDict) {  
    boolean[] dp = new boolean[s.length() + 1];  
    dp[0] = true;  
  
    for (int i = 1; i < dp.length; i++) {  
        for (String word : wordDict) {  
            int len = word.length();  
            if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {  
                dp[i] = true;  
                break;  
            }  
        }  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[s.length()];  
}

// 回溯记忆法
class Solution {
    private Set<String> set;
    private int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        set = new HashSet<>(wordDict);
        return backtracking(s, 0);
    }

    public boolean backtracking(String s, int startIndex) {
        // System.out.println(startIndex);
        if (startIndex == s.length()) {
            return true;
        }
        if (memo[startIndex] == -1) {
            return false;
        }

        for (int i = startIndex; i < s.length(); i++) {
            String sub = s.substring(startIndex, i + 1);
		    // 拆分出来的单词无法匹配
            if (!set.contains(sub)) {
                continue;                
            }
            boolean res = backtracking(s, i + 1);
            if (res) return true;
        }
        // 这里是关键，找遍了startIndex~s.length()也没能完全匹配，标记从startIndex开始不能找到
        memo[startIndex] = -1;
        return false;
    }
}