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

入营第三十八天
难度：难

• 计划任务
• 完成任务

322. 零钱兑换

动态规划五部曲：
1.确定dp数组以及下标含义 dp[j]代表凑足金额为[j]的所需最少硬币个数
2.确定递推公式 dp[j] = min(dp[j-coins[i]+1,dp[j])
3.递推数组初始化 dp[0] = 0;
4.确定遍历顺序
5.举例推导递推公式

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.完全平方数

动态规划五部曲：
1.确定dp数组以及下标含义 dp[j]代表凑成n使用的最少完全平方数的个数
2.确定递推公式 dp[j]=Math.min(dp[j],dp[j-(i*i)]+1);
3.递推数组初始化
4.确定遍历顺序
5.举例推导递推公式

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];int max = Integer.MAX_VALUE;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.单词拆分

题意转换：单词->物品 字符串->背包容量
判断条件是关键 substring方法都为小写
动态规划五部曲：
1.确定dp数组以及下标含义 dp[i] 代表字符串长度为i时，是否可以拆分成字典里面出现的单词（一个或多个）
2.确定递推公式 if(dp[j,i]==true && dp[j] == true) dp[i]=true
3.递推数组初始化
4.确定遍历顺序
5.举例推导递推公式

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0]=true;for(int i=1;i<=s.length();i++){for(String word:wordDict){int len = word.length();if(i>=len && dp[i-len] && word.equals(s.substring(i-len,i))){dp[i]=true;break;}}}return dp[s.length()];}
}