力扣 每日一题 518. 零钱兑换 II

今天的是一个中等题,主要考点是动态规划,微软面试考过这个。

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

 

题目中,每个面额的硬币可以用无限个,等同于给定一个数组,计算出能够组合出target的组合数。每个数有两种选择,可以加入计算,也可以不加入计算,这种就是可以用深度优先算法的信号,遍历每一种可能,计算最终结果,如果等于amount,则结果加1。

深度优先算法(DFS)的复杂度一般比较高,大部分会超时,解决方案无非就是剪枝,或者是改变策略,从底向上计算,利用动态规划来解决。如果一时想不到动态规划的版本,可以先写出DFS的版本,找出一些线索,也可以让面试官觉得你的功底和反应还是可以的。

我们今天就给出动态规划的思路,就不写DFS版本了。

1.如果amount是0,则结果为1,因为什么都不取,也是一种组合。

2.以示例为例,如果我们需要知道amount为5的组合数,我们可以将4(5-1),3(5-2),0(5-5)的组合数相加。而4的组合数也使用同样的方法,将3(4-1),2(4-2)的组合数相加即可。

根据上述分析,我们可以先开一个二维数组,

int[][] dp = new int[amount+1][n];
初始状态是dp[0][*]=1;
转换方式是dp[i][j]+=dp[i-coins[j]][j]+dp[i][j-1];

最终代码版本

 1  public int changeDp(int amount, int[] coins){
 2         int n = coins.length;
 3         int[][] dp = new int[amount+1][n];
 4         for(int i =0;i<n;i++){
 5             dp[0][i]=1;
 6         }
 7         for(int i=1;i<=amount;i++){
 8             for(int j = 0;j<n;j++){
 9                 if(j>0) {
10                     dp[i][j] += dp[i][j - 1];
11                 }
12                 if(i>=coins[j]){
13                     dp[i][j]+=dp[i-coins[j]][j];
14                 }
15             }
16         }
17         return dp[amount][n-1];
18     }

效率击败7%,看上去有点低,也没有做空间上的优化,不过面试的时候,先写出来,然后优化,心里也不慌了

上一篇:518. 零钱兑换 II


下一篇:leetcode-518:零钱兑换 II