9.8---硬币问题（CC150）

这道题卡了一天。要想AC非常难。

1，第一个解决办法，优化暴力：

public class Coins {
   public static int countWays(int n){
    int num25 = n / 25;
    long res = 0;
    for(int i = 0; i <= num25;i++){
        int leave25 = n - i * 25;
        int num10 = leave25 / 10;
        for(int j = 0; j <= num10; j++){
            int leave10 = leave25 - j * 10;
            int num5 = leave10 / 5;
            res += num5 + 1;
            res = res % 1000000007;
        }
    }
    return (int) res;
        
    }
}

2，第二个解决办法，递推式：

但是LTE。

dp[i][sum] = 用前i种硬币构成sum 的所有组合数。

http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html

    public static int myCountWays(int n){
        int[][] dp = new int[5][n+1];
        int[] coins = {1,5,10,25};
        for(int i = 0; i <= 4; i++){
            dp[i][0] = 1;
        }
        for (int i = 1; i <= 4; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = 0;
                for (int k = 0; k <= j / coins[i-1]; ++k)
                {
                    dp[i][j] += dp[i-1][j - k * coins[i-1]];
                }
            }
        }
        return dp[4][n];
    }

3，最好的答案：

    public static  int countWays(int n) {
        // write code here
        int[] coins={1,5,10,25};
        int[] dp = new int[100001];      
        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];
    }

目前的理解是：

如果只有面值1，那么所有值都是1.

如果有两种面值1,5.那么dp[i] = dp[i] + dp[i - 5];从5开始算。

所以。