多少种分类

[编程题]多少种分类

热度指数：13436 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知正整数n，将其分为0到多个25、10、5、1这四个数的和。如n为11可分为一个10和一个1，或者分为两个5和一个1。返回n有多少种分法。保证n小于等于100000，请将答案Mod 1000000007以防止溢出。

测试样例：

返回：2

算法知识视频讲解

推荐

0pandas0

class Coins {
public:
    int countWays(int n) {
        // write code here
    	int coins[4]={1,5,10,25};
        int dp[100001] = {0};        
        dp[0] = 1;
        for(int i = 0;i < 4;++i){
            for(int j = coins[i];j <= n;++j){
                dp[j] =(dp[j]+dp[j-coins[i]])%1000000007;                
            }
        }
        return dp[n]; 
    }
};

编辑于 2015-08-27 16:57:12 回复(25)