代码随想录算法训练营第三十八天 | 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()];}
}