【Lintcode】279. Number of Ways to Represent N Cents

Number of Ways to Represent N Cents"/>

【Lintcode】279. Number of Ways to Represent N Cents

题目地址：

给定一个 n n n，表示 n n n元钱，现在有无限枚面值 1 1 1、 5 5 5、 10 10 10和 25 25 25元的硬币，问 n n n可以用这些硬币表示的方式的数目。一个表示指的是一个四元组 ( x 1 , x 2 , x 3 , x 4 ) (x_1,x_2,x_3,x_4) (x1​,x2​,x3​,x4​)使得 x 1 + 5 x 2 + 10 x 3 + 25 x 4 = n x_1+5x_2+10x_3+25x_4=n x1​+5x2​+10x3​+25x4​=n。

思路是动态规划。我们可以将一个表示等价于一个单调增序列，例如 ( 1 , 2 , 3 , 1 ) (1,2,3,1) (1,2,3,1)就可以表示为 [ 1 , 5 , 5 , 10 , 10 , 10 , 25 ] [1,5,5,10,10,10,25] [1,5,5,10,10,10,25]。令 f [ n ] f[n] f[n]表示和为 n n n的且只由 1 1 1、 5 5 5、 10 10 10和 25 25 25构成的单调增序列的个数。按照定义 f [ 0 ] = 1 f[0]=1 f[0]=1（相当于空序列）， f [ n ] = 0 f[n]=0 f[n]=0如果 n < 0 n<0 n<0。那么这些序列可以分为四个不相交的集合，按照以哪个数字结尾来划分。所以容易知道： f [ n ] = f [ n − 25 ] + f [ n − 10 ] + f [ n − 5 ] + f [ n − 1 ] f[n]=f[n-25]+f[n-10]+f[n-5]+f[n-1] f[n]=f[n−25]+f[n−10]+f[n−5]+f[n−1]代码如下：

public class Solution {/*** @param n: An integer* @return: An integer*/public int waysNCents(int n) {// write your code hereint[] dp = new int[n + 1];dp[0] = 1;int[] coins = {1, 5, 10, 25};for (int i = 0; i < coins.length; i++) {for (int j = 1; j <= n; j++) {if (j >= coins[i]) {dp[j] += dp[j - coins[i]];}}}return dp[n];}
}

时空复杂度 O ( n ) O(n) O(n)。

注解：注意程序的实现方式。第一层循环是枚举的序列最后一个数字是多少，然后把coins[i]结尾的序列的个数累加到dp[j]上去。当然这里也可以用二维dp来做，比如设 f [ i ] [ j ] f[i][j] f[i][j]是只用前 i i i个硬币拼出 j j j元的方式数。则 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − A [ i ] ] f[i][j]=f[i-1][j]+f[i][j-A[i]] f[i][j]=f[i−1][j]+f[i][j−A[i]]其中 f [ 0 ] [ 0 ] = 1 , f [ 0 ] [ j ] = 0 , j > 0 f[0][0]=1,f[0][j]=0, j>0 f[0][0]=1,f[0][j]=0,j>0。两重循环递推即可。