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

322. 零钱兑换 

题目链接：322. 零钱兑换 - 力扣（LeetCode）

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount+1];
        for(int i = 0; i < dp.length; i++){
            dp[i] = 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], dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
        
    }
}

 279.完全平方数

题目链接：279. 完全平方数 - 力扣（LeetCode）

class Solution {
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n+1];
        for(int i = 0; i < dp.length; i++){
            dp[i] = max;
        }
        dp[0] = 0;

        for(int i = 1; i * i <= n; i++){
            for(int j = i * i; j <= n; j++){
                dp[j] = Math.min(dp[j],dp[j- i * i]+1);
            }
        }
        return dp[n];
    }
}

 139.单词拆分

题目链接：139. 单词拆分 - 力扣（LeetCode）

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

原文地址：https://blog.csdn.net/qq_51792424/article/details/144301798

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！