●322. 零钱兑换
我现在越来越觉得是不是得好好用手去走一遍流程了。。。。。
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount+1];
for (int j = 0; j < dp.length; j++) {
dp[j] = 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.完全平方数
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i = 0;i<=n;i++){
dp[i] = n+1;
}
dp[0]=0;//dp[0]表示 和为0的完全平方数的最小数量,那么dp[0]一定是0。
//有同学问题,那0 * 0 也算是一种啊,为啥dp[0] 就是 0呢?
//看题目描述,找到若干个完全平方数(比如 1, 4, 9, 16, ...),题目描述中可没说要从0开始,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.单词拆分
这题还是不明白;
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()];
}
}