难度中等547收藏分享切换为英文关注反馈
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
1
2
3
| 输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
|
示例 2:
1
2
| 输入: coins = [2], amount = 3
输出: -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| 0。 贪心+dfs非常快
class Solution {
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
coinChange(coins.length-1, coins, 0, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private void coinChange(int index, int[] coins, int count, int needAmount) {
if (needAmount == 0) {
ans = Math.min(count, ans);
return;
}
if (index < 0) {
return;
}
int i = needAmount / coins[index];
for (int k=i; k>=0 && count+k<ans; k--) {
coinChange(index-1, coins, count+k, needAmount-k*coins[index]);
}
}
}
1.动态规划第二快
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
2.递归升级版很慢
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) return -1;
if (rem == 0) return 0;
if (count[rem - 1] != 0) return count[rem - 1];
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min)
min = 1 + res;
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
4自底向上dp自己写的
class Solution {
public int coinChange(int[] coins, int amount) {
int max=amount+1;
int[] dp=new int[max];
Arrays.fill(dp, max);
dp[0]=0;
for(int i=1;i<max;i++){
for(int coin: coins){
if(i>=coin){
dp[i]=Math.min(dp[i],dp[i-coin]+1);
}
}
}
return (dp[amount]>amount)? -1:dp[amount];
}
}
|
难度中等246收藏分享切换为英文关注反馈
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
1
2
3
4
5
| 输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
|
示例 2:
1
2
3
4
5
| 输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 1. dfs+剪枝
class Solution {
public boolean canPartition(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int n : nums){
sum += n;
}
if ((sum % 2) == 1){
return false;
}
sum /= 2;
return canPartition(nums, nums.length-1, sum, sum);
}
private boolean canPartition(int[] nums, int idx, int had, int pass){
if (had == 0 || pass == 0){
return true;
}
else if (had < 0 || pass < 0){
return false;
}
else{
return canPartition(nums, idx-1, had-nums[idx], pass) || canPartition(nums, idx-1, had, pass-nums[idx]);
}
}
}
|
作为“0-1 背包问题”，它的特点是：“每个数只能用一次”。思路是：物品一个一个选，容量也一点一点放大考虑（这一点是“动态规划”的思想，特别重要）。
如果在实际生活中，其实我们也是这样做的，一个一个尝试把候选物品放入“背包”，看什么时候能容纳的价值最大。
具体做法是：画一个 len 行，target + 1 列的表格。这里 len 是物品的个数，target 是背包的容量。len 行表示一个一个物品考虑，target + 1多出来的那 1 列，表示背包容量从 0 开始，很多时候，我们需要考虑这个容量为 0 的数值。
状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
状态转移方程：很多时候，状态转移方程思考的角度是“分类讨论”，对于“0-1 背包问题”而言就是“当前考虑到的数字选与不选”。
1、不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
2、选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
状态转移方程是：
1
| dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
|
一般写出状态转移方程以后，就需要考虑边界条件（一般而言也是初始化条件）。
1、j - nums[i] 作为数组的下标，一定得保证大于等于 0 ，因此 nums[i] <= j；
2、注意到一种非常特殊的情况：j 恰好等于 nums[i]，即单独 nums[j] 这个数恰好等于此时“背包的容积” j，这也是符合题意的。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public boolean canPartition(int[] nums) {
int len=nums.length;
int sum=0;
for(int num: nums)
sum+=num;
if(sum%2==1)
return false;
int target=sum/2;
boolean[][] dp=new boolean[len][target+1];
if(nums[0]<=target)
dp[0][nums[0]]=true;
for(int i=1; i<len;i++){
for(int j=0;j<target+1;j++){
dp[i][j]=dp[i-1][j];
if(j==nums[i]){
dp[i][j]=true;
}
if(nums[i]<j){
dp[i][j]= dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
}
return dp[len-1][target];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public boolean canPartition(int[] nums) {
int len=nums.length;
int sum=0;
for(int num: nums)
sum+=num;
if(sum%2==1)
return false;
int target=sum/2;
boolean[] dp=new boolean[target+1];
if(nums[0]<=target)
dp[nums[0]]=true;
for(int i=1; i<len;i++){
for(int j=target;nums[i]<j;j--){
if(dp[target]){
dp[j]=true;
}
dp[j]= dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
}
|