dp 类找零钱类问题
这类问题，需要维护，之前的状态，当前的状态是 （当前 - 当前值） 的上一个状态的最值相关
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
输入: coins = [2], amount = 3 输出: -1
// 贪心思想，零钱兑换， 和平方求和的题目类似
public int coinChange(int[] coins, int amount) {
if(coins == null || coins.length == 0){
return -1;
}
Arrays.sort(coins);
int[] dp = new int[amount+1];
for (int i=1;i<amount+1;i++){
int min = amount +1;
for (int j=0;j<coins.length;j++){
if (coins[j] > i){
break;
}
// 只需要处理当前值得状态，不需要管怎么计算
min = Math.min(min,dp[i-coins[j]] + 1);
}
dp[i] = min;
}
if (dp[amount] == amount+1){
return -1;
}
return dp[amount];
}279 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.
public int numSquares(int n) {
int sqareLen = (int)(Math.sqrt(n));
int[] numSqare = new int[sqareLen];
for(int i=1;i<=sqareLen;i++){
numSqare[i-1] = i * i;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
int count = n+1;
for(int j=0;j < sqareLen && numSqare[j]<= i;j++){
count = Math.min(count,dp[i-numSqare[j]]+1);
}
dp[i] = count;
}
return dp[n];
}- 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 使用背包问题的动态规划进行求解
boolean[][] dp = new boolean[nums.length][sum/2+1];
int target = sum/2;
if(nums[0] <= target){
dp[0][nums[0]] = true;
}
for(int i=1;i<nums.length;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i]<=j){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
if(dp[i][target]){
return true;
}
}
return dp[nums.length-1][target];
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录