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

322. 零钱兑换

https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

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

279.完全平方数

https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

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

139.单词拆分

https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

思路:
排列题要用爬楼梯的思路做.

 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()];
    }