题解 | #兑换零钱(二)#
兑换零钱(二)
http://www.nowcoder.com/practice/521cead04d1442899767578c3aa395f0
题意：
给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额，请你计算并返回可以凑出总金额的的组合数。
如果凑不出 target 则返回 0。
方法一：
动态规划（完全背包）
思路：dp[i]表示硬币凑成 i 的组合数。不同数额的硬币可以取任意个凑成target总金额，因此是完全背包问题。
class Solution {
public:
int dp[50005]={0};//dp[i]表示凑成i的组合数
int change(int target, vector<int>& nums) {
int n=nums.size();
dp[0]=1;//初始化
for(int i=0;i<n;i++){//完全背包
for(int j=nums[i];j<=target;j++){
dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
};
时间复杂度：%2C%E4%BA%8C%E9%87%8D%E5%BE%AA%E7%8E%AF%E3%80%82)
空间复杂度：%2C%E5%AD%98%E5%82%A8%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84%E3%80%82)
方法二：
java
思路：java实现。
import java.util.*;
public class Solution {
public int change (int target, int[] nums) {
int[] dp=new int[target+1];//dp[i]表示凑成i的组合数
int n=nums.length;
dp[0]=1;//初始化
for(int i=0;i<n;i++){//完全背包
for(int j=nums[i];j<=target;j++){
dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
}
时间复杂度：空间复杂度：
查看8道真题和解析
