代码随想录算法训练营 | 322. 零钱兑换，279.完全平方数，139.单词拆分

322. 零钱兑换
题目链接：322. 零钱兑换
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰零钱兑换
日期：2024-10-12

想法：完全背包，注意初始化除dp[0]外都要置为Integer.MAX_VALUE，才能后面选出最小值，还有判断dp[j - coins[i]] != Integer.MAX_VALUE，不成立的化代表除去coins[i]后，没有符合的结果，直接跳过。
Java代码如下：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for(int i = 0; i <= amount; i++) {
            dp[i] = 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.完全平方数
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰完全平方数
日期：2024-10-12

想法：跟上一题差不多
Java代码如下：

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

总结：确认i范围没反应过来，i^2小于等于n就行了。

139.单词拆分
题目链接：139.单词拆分
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰单词拆分
日期：2024-10-12

想法：本质是组合，先背包后物品。
Java代码如下：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !valid[i]; j++) {
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }
}