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开始算。

所以。

巴特西

9.8---硬币问题（CC150）

最新文章

热门文章