1. 零钱问题
1.1 返回最小的硬币数量
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
递归：
/**
* 固定参数：可选的硬币组coins
*
*
* 可变参数：rest的钱需要凑
*
* 方案含义：还有rest钱需要凑的最小硬币数
*
* @return
*/
private int process(int[] coins, int restAmount){
//bad case
if(restAmount < 0){
return -1;
}
if(restAmount == 0){
return 0;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
//选择当前硬币
int p1 = process(coins,restAmount - coins[i]);
if(p1 != -1){
//能选的话，硬币数+1，同时和当前的最小硬币数比较
res = Math.min(p1+1, res);
}
}
return res;
}
动态规划：
private int processDp(int[] coins, int amount){
//1.问题定义
int[] dp = new int[amount+1];
for (int i = 0; i <= amount; i++) {
//这里不能用int.max, 下面+1会超出int范围，所以使用一个比amount大的值就可以
dp[i] = amount + 1;
}
//2.边界问题
dp[0] = 0;
//3.状态方程, 从左到右填表
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if(i - coins[j] >= 0){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
//返回结果
return dp[amount] >amount ? -1 : dp[amount];
}
1.2 返回组合数
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个
思路：
这时一道完全背包的问题，解法为：只要不超过背包的剩余容量就一直往里尝试装
递归：
/**
* 方法含义：
* 在coins上[0...cur]上选择，刚好凑出restAmount钱 的组合数，
*
* @param coins
* @param restAmount
* @return
*/
public int process(int[] coins, int cur, int restAmount){
//base case
//剩余钱刚好为0，组合数为1
if(restAmount == 0){
return 1;
}
//证明组合不出来
if(restAmount < 0 || cur == -1){
return 0;
}
if(restAmount < coins[cur]){
//不选, 在[cur-1]给我凑出来restAmount来，并给我返回组合数
int p2 = process(coins, cur - 1, restAmount);
return p2;
}else {
//选, 就重复选
int p3 = 0;
for (int i = 0; i * coins[cur] <= restAmount ; i++) {
//选, 在[cur-1]给我凑出来restAmount-i * coins[cur]来，并给我返回组合数
p3 += process(coins, cur-1, restAmount - i * coins[cur]);
}
return p3;
}
}
public int processUpgrade(int[] coins, int cur, int restAmount){
//base case
//剩余钱刚好为0，组合数为1
if(restAmount == 0){
return 1;
}
//组合不出来
if(restAmount < 0 || cur == -1){
return 0;
}
int res=0;
for (int i = 0; i * coins[cur] <= restAmount ; i++) {
res += processUpgrade(coins, cur-1, restAmount- i * coins[cur]);
}
return res;
}
动态规划：
private int processDp(int[] coins, int amount){
//1.问题定义
//dp[cur][rest] 为在coins[0,cur]上选择，刚好凑出restAmount钱 的组合数
//cur:-1~coins.length-1，大小为coins.length+1. rest：0～amount, 大小amount+1
int[][]dp = new int[coins.length+1][amount+1];
//2.边界
for (int cur = 0; cur <= coins.length; cur++) {
for (int rest = 0; rest <= amount; rest++) {
//base case, 剩余钱刚好为0，组合数为1
if(rest==0){
dp[cur][rest] = 1;
}
}
}
//3.转移方程, 从上到下 从左到右
for (int cur = 1; cur <= coins.length; cur++) {
for (int rest = 1; rest <= amount; rest++) {
for (int i = 0; i * getCoinsValue(coins, cur) <= rest ; i++) {
//选, 在[cur-1]给我凑出来restAmount-i * coins[cur]来，并给我返回组合数
dp[cur][rest] += dp[cur-1][rest - i * getCoinsValue(coins, cur)];
}
}
}
//4.返回结果
return dp[coins.length][amount];
}
/**
* dp[-1][0] == 0, 不方便操作，所以改为dp[0][0] == 0，转变后cur要-1，再去值
*/
private int getCoinsValue(int[] coins, int cur){
return coins[cur - 1];
}
2. 组合数问题
2.1 target组合数（顺序不同的序列被视作不同的组合）
题目：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
思路：
尝试的关键在于：每次都需要从nums数组中去选，然后去拼凑剩余的rest-nums[i], 以此累加
递归思路：
/**
* 固定参数：nums
*
* 可变参数：rest
*
* 方案含义：返回在nums上选择数，元素之和为rest的组合数
*/
private int process(int[] nums, int rest){
//base case 代表组合出来了
if(rest == 0){
return 1;
}
//依赖关系
int ans = 0;
//从nums上按个选
for (int i = 0; i < nums.length; i++) {
//如果能选
if(rest >= nums[i]){
//选了nums[i], 剩下rest - nums[i] 从nums上选择的元素和的组合数，返回来
//当前rest = 4 可以：选了1 + f(3) 或者 选了3 + f(1)
ans+= process(nums, rest - nums[i]);
}
}
return ans;
}
动态规划：
private int processDp(int[] nums, int target){
//1.问题定义
//dp[rest] 是在nums上选数，元素之和为rest的组合数
//rest：0～target，大小：target+1
int dp[] = new int[target + 1];
//2.边界问题
dp[0] = 1;
//3.转移方程，从左到右
for (int rest = 1; rest <= target; rest++) {
for (int i = 0; i < nums.length; i++) {
//如果能选
if(rest >= nums[i]){
dp[rest] += dp[rest - nums[i]];
}
}
}
//4.返回结果
return dp[target];
}
2.2 目标和（在数组中选择+和-组合出target）
题目：
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：
从左到右尝试，cur必选，看cur上选+，还是选-
递归：
/**
*
* 方法含义：在nums[0, cur]上对元素选择+和—，元素之和为rest的组合数，
*
* @return
*/
private int process(int[] nums, int cur, int rest){
//base case, 当rest = 0时，cur也必须选完
if(rest == 0 && cur == -1){
return 1;
}
//边界
if(cur == -1){
return 0;
}
int ans = 0;
//p1: 当前选择的符号为 + , 还需要凑出 rest - nums[cur] 来
ans += process(nums, cur-1, rest - nums[cur]);
//p2: 当前选择的符号为 - , 还需要凑出 rest + nums[cur] 来
ans += process(nums, cur-1, rest + nums[cur]);
return ans;
}
动态规划：
private int processDp1(int[] nums, int target){
//1.问题定义
//dp[cur][rest] 从nums[0,cur]上选择数据，选完刚好凑成rest的组合数
//cur: -1 ~ nums.length，大小为length+1
//rest：-sum ～ target + sum, 大小为: sum + 1 + target + sum
int s = 0;
for (int i = 0; i < nums.length; i++) {
s += nums[i];
}
int restLength = s + 1 + Math.abs(target) + s;
int[][] dp = new int[nums.length + 1][restLength];
//2.边界, rest=0的位置，需要进行下标转换
int restZeroIndex = target < 0 ? restLength-s-1 : s;
dp[0][restZeroIndex] = 1;
//3.转移方程，从上到下，从左到右
for (int cur = 1; cur <= nums.length; cur++) {
for (int rest = 0; rest < restLength; rest++) {
//p1: 当前选择的符号为 + , 还需要凑出 rest - nums[cur] 来（需要做边界控制）
int p1 = indexIsValid(rest - getValue(nums,cur), restLength) ? dp[cur-1][rest - getValue(nums,cur)] : 0;
//p2: 当前选择的符号为 - , 还需要凑出 rest + nums[cur] 来（需要做边界控制）
int p2 = indexIsValid(rest + getValue(nums,cur), restLength) ? dp[cur-1][rest + getValue(nums,cur)] : 0;
dp[cur][rest] = p1 + p2;
}
}
//4.返回结果：rest=target的位置，需要进行下标转换,
int restTargetIndex = target < 0 ? s : s + target;
return dp[nums.length][restTargetIndex];
}
