题目主要信息

给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额，请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0

方法一：DFS

具体方法

使用DFS递归和回溯的方法。dfs方法中有三个参数，分别是nums数组，索引和target，在递归的过程中用$target-nums[i]target-nums[i]$ ，当$target=0target=0$时，说明找到一种方法，返回1 即可，一直遍历下去找到所有的结果，但是由于本题数据较多，会超时。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int change (int target, int[] nums) {
        // write code here
        return dfs(nums, 0, target);
    }
      public  int dfs(int[] coins, int i, int amount) {
        //金额为0，直接返回1
        if (amount == 0)
            return 1;
        //金额小于0，或者没有可选的硬币了，返回0
        if (amount < 0 || i == coins.length)
            return 0;
        int res = 0;
        //每种硬币有两种状态，选和不选
        //不选当前硬币
        res += dfs(coins, i + 1, amount);
        //选当前硬币,注意这里选的时候i没变，也就是说下次还
        //可以再选，因为每个硬币可以选择无数次
        res += dfs(coins, i, amount - coins[i]);
        return res;
    }

}

复杂度分析

复杂度分析

• 时间复杂度：$O(n\ast 2^n)O(n*\; 2^n)$,因为每一个元素的状态无外乎取与不取，一共$2^{n}2^n$种状态，每种状态都需要$O(n)O(n)$的构造时间。
• 空间复杂度：$O(n)O(n)$,递归深度为n

方法二：动态规划

具体方法

本题是一个完全背包的问题，所以可以使用动态规划来做，设一个dp数组，$dp[i]dp[i]$表示 可以兑换成i的组合数。

• $\mathrm{初}\mathrm{始}\mathrm{化}dp[0]=1初始化dp[0]\; =\; 1$

• 遍历nums,对其中每个元素num，进行下面的操作

  • $\mathrm{遍}\mathrm{历}i\mathrm{从}num\mathrm{到}target\mathrm{，}\mathrm{将}dp[i-num]\mathrm{的}\mathrm{值}\mathrm{加}\mathrm{到}dp[i]遍历i从num到target，将dp[i-num]的值加到dp[i]$

  最终返回$dp[target]dp[target]$

代码实现

import java.util.*;


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

}

复杂度分析

• 时间复杂度：$O(target\times n)O(target\times \; n)$其中$targettarget$是总金额，n 是数组 nums的长度。需要使用数组nums中的每个元素遍历并更新数组 $dpdp$中的每个元素的值。

• 空间复杂度：$O(target)O(target)$，其中$targettarget$是总金额。需要创建长度为$target+1\mathrm{的}\mathrm{数}\mathrm{组}dptarget+1\; 的数组dp$。