今天的是一个中等题,主要考点是动态规划,微软面试考过这个。
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例
输入: 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%,看上去有点低,也没有做空间上的优化,不过面试的时候,先写出来,然后优化,心里也不慌了