旅游网站html模板,广西网站建设流程,公司网站 英文,沈阳网络科技公司排名322. 零钱兑换 题目链接#xff1a;322. 零钱兑换 文档讲解#xff1a;代码随想录 状态#xff1a;能想到凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]#xff0c;但没想到加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]#xff08;考虑coins[i]#xff09…322. 零钱兑换 题目链接322. 零钱兑换 文档讲解代码随想录 状态能想到凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]但没想到加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i] 思路 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i] 所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。 递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);
注意事项 考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。 然后凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;
题解
public int coinChange(int[] coins, int amount) {// 创建一个数组dp大小为amount 1用于存储到达每个金额的最小硬币数int[] dp new int[amount 1];// 将dp数组初始化为一个较大的值表示这些金额暂时无法通过给定的硬币组成Arrays.fill(dp, Integer.MAX_VALUE);// 如果金额为0则不需要任何硬币dp[0] 0;// 遍历每一种硬币面值for (int coin : coins) {// 对于每一种硬币从它的面值开始直到amount更新dp数组for (int j coin; j amount; j) {// 如果使用当前硬币可以减少硬币数则更新dp[j]if (dp[j - coin] ! Integer.MAX_VALUE) {dp[j] Math.min(dp[j], dp[j - coin] 1);}}}// 如果dp[amount]仍为初始值则表示无法用给定的硬币凑出amount返回-1return dp[amount] Integer.MAX_VALUE ? -1 : dp[amount];
}
279.完全平方数 题目链接279.完全平方数 文档讲解代码随想录 状态做过上道题后感觉还行 思路 dp[j]和为j的完全平方数的最少数量为dp[j] dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。 此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]);
题解
public int numSquares(int n) {// 创建一个大小为n 1的数组dp用于存储到达每个数所需的最少完全平方数数量int[] dp new int[n 1];// 将dp数组初始化为一个较大的值表示这些数暂时无法通过完全平方数组成Arrays.fill(dp, Integer.MAX_VALUE);// 如果数字为0则不需要任何完全平方数dp[0] 0;// 遍历所有可能的完全平方数for (int i 1; i Math.sqrt(n); i) {// 对于每一个完全平方数从它的值开始直到n更新dp数组for (int j i * i; j n; j) {// 如果使用当前完全平方数可以减少完全平方数的数量则更新dp[j]dp[j] Math.min(dp[j], dp[j - i * i] 1);}}// 返回dp[n]即为达到数字n所需的最少完全平方数数量return dp[n];
}
139.单词拆分 题目链接139.单词拆分 文档讲解代码随想录 状态不会 思路 单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。 拆分时可以重复使用字典中的单词说明就是一个完全背包
dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。
如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是truej i 。 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
题解
public boolean wordBreak(String s, ListString wordDict) {// 将wordDict转换为一个HashSet便于查找HashSetString set new HashSet(wordDict);// 动态规划数组boolean[] dp new boolean[s.length() 1];dp[0] true;// 遍历s的每个子串for (int i 1; i s.length(); i) {for (int j 0; j i; j) {// 如果子串s[j:i]在字典中且dp[j]为true则dp[i]设为trueif (dp[j] set.contains(s.substring(j, i))) {dp[i] true;break;}}}// 返回结果return dp[s.length()];}
