已知正整数n,将其分为0到多个25、10、5、1这四个数的和。如n为11可分为一个10和一个1,或者分为两个5和一个1。返回n有多少种分法。保证n小于等于100000,请将答案Mod 1000000007以防止溢出。
测试样例:
6
返回:2
# -*- 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]