兑换零钱(二)

1. rest=0，就表示形成了一种有效的方案；
2. rest<0，当前的凑钱方案不合法，直接返回0；
3. rest>0，使用递归从当前depth开始的面额继续凑目标值。

private int recurrent(int[] nums, int depth, int rest, int[][] mem) {
    if(rest < 0){
        return 0;
    }
    if(rest == 0){
        return 1;
    }
    if(mem[depth][rest] > 0) return mem[depth][rest];
    for(int i = depth; i < nums.length; i++){
        mem[depth][rest] += recurrent(nums, i, rest - nums[i], mem);
    }
    return mem[depth][rest];
}

动态规划

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int change (int target, int[] nums) {
        // write code here
        int n = nums.length;
        int[][] dp = new int[n][target + 1];
        for(int i = 0; i < n; i++){
            dp[i][0] = 1;
        }
        for(int i = n - 1; i >= 0; i--){
            for(int j = nums[i]; j <= target; j++){
                dp[i][j] = (i < n - 1? dp[i + 1][j]: 0) + dp[i][j - nums[i]];
            }
        }
        return dp[0][target];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int change (int target, int[] nums) {
        // write code here
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = n - 1; i >= 0; i--){
            for(int j = nums[i]; j <= target; j++){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}