面试题 08.11

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents. (The result may be large, so you should return it modulo 1000000007)

Example1:

Input: n = 5 Output: 2 Explanation: There are two ways: 5=5 5=1+1+1+1+1 Example2:

Input: n = 10 Output: 4 Explanation: There are four ways: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1 Notes:

You can assume:

0 <= n <= 1000000

Solutions

Similar to knapsack problem.

1. dynamic programming

2. Why can not iterate over n sents at the first loop ?

   • For example: 1 + 5 = 6 and 5 + 1 = 6 would be counted twice when solving dp[6].

class Solution {
public:
    int waysToChange(int n) {
        vector<size_t> dp(n + 1);
        dp[0] = 1;
        for (auto coin : {1, 5, 10, 25}) {
            for (int cur = 1; cur <= n; cur++) {
                if (cur - coin >= 0 && dp[cur - coin])
                    dp[cur] = (dp[cur] + dp[cur - coin]) % 1000000007;;
            }
        }

        return dp[n];
    }
};