多少种分类

[编程题]多少种分类

热度指数：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)

Python

BiangTiu

def countWays(self, n):
    if n < 1:
        return 0
    dp = [0] * (n+1)
    state = [1, 5, 10, 25]
    dp[0] = 1
    for s in state:
        for i in range(s, n+1):
            dp[i] = (dp[i] + dp[i-s]) % 1000000007
    return dp[n]

发表于 2021-10-14 20:24:42 回复(0)

Python

Yannyezixin

# -*- coding:utf-8 -*-
class Coins:
    def countWays(self, n):
        coins = [1, 5, 10, 25]
        dp = [0 for i in range(n + 1)]
        dp[0] = 1
        
        for i in range(4):
            for j in range(coins[i], n + 1):
                dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007
        return dp[n]

发表于 2016-08-05 17:55:17 回复(0)