322. 零钱兑换

1、题目描述

2、题目分析 

       本题也是【动态规划】的经典题目，之前对【找零钱】问题，专门写了一个专题，该专题对此类问题进行了比较详细的分析，有兴趣的可以之间看下这个专题，链接如下：

       算法分享系列No.8--(大厂面试实际场景算法题)---找零钱 问题

       

      针对本题，专门分析相关思路，找零钱【数组】【动态规划】。

      动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。动态规划具备的特征：最优子结构性质，无后效性，子问题的重叠性。

      针对本题的解决思路，具体做法如下：

• step 1：可以用dp[i] 表示要凑出i元钱需要最小的货币数。
• step 2：一开始都设置为最大值aim+1 ，因此货币最小1元，即货币数不会超过aim 
• step 3：初始化dp[0]=0。
• step 4（难点，找到转移递推公式）：后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，转移方程为 dp[i]=min(dp[i],dp[i−arr[j]]+1)
• step 5：最后比较dp[aim] 的值是否超过aim，如果超过说明无解，否则返回即可。

    

     实现代码如下：

class Solution {
    public int coinChange(int[] coins, int amount) {
       //按照资金数设置
       int maxV = amount+1; 

       //设置辅助空间dp: dp【i】代表含义目标钱数为i的时候，最少钱币数是多少
       int[] dp = new int[maxV];
       Arrays.fill(dp,maxV);

       //初始化，当资金为0时，此时自然用到0张钱币
       dp[0] = 0;
       for(int i = 1; i < maxV; 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]; 

    }
}

复杂度分析

时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。数组 dp 需要开长度为总金额 S 的空间。

        这个题目也是【0-1】背包的一个转移题目，如果在这个题目仍然理解有疑问的，可以参考下之前梳理的专题博文（链接如下： 算法分享系列No.8--(大厂面试实际场景算法题)---找零钱 问题），中，对一个case专门进行了打印输出，  部分截图如下（详情请看链接内容，专题博文中对这个打印输出是完整的）。