题目大意：

有5种硬币， 面值分别为1、5、10、25、50，现在给出金额，问可以用多少种方式组成该面值。

 

解题思路：

首先我们可以想到，用这些硬币组成11有多少种．

就是组成10的种数，加上组成６的种数，加上组成１的种数，因为这些面值都是加上一枚硬币就得到11了.

然后我们又能继续去求1组成10的种数,那么明显就是9,5,0的组成数的和.

需要注意的是1+5自底向上的方法，需要注意的是1+5和5+1是一种的，所以要处理一下，从小往大排就不会错了。

 

这道题我还不是很懂，以后再看看。                           >>>

 

记忆化搜索：很白痴的算法，直接交给下一层去算，算完记录下来以免之后重复算。

#include 
     
        #include 
      
         const int MAXN = 8000;  const int coin[5] = {
   1, 5, 10, 25, 50};  int n;  long long dp[MAXN][5];    long long solve(int i, int s) {      if (dp[s][i] != -1)          return dp[s][i];      dp[s][i] = 0;      for (int j = i; j < 5 && s >= coin[j]; j++)          dp[s][i] += solve(j, s - coin[j]);      return dp[s][i];  }    int main() {      memset(dp, -1, sizeof(dp));      for (int i = 0; i < 5; i++)          dp[0][i] = 1;      while (scanf("%d", &n) != EOF)          printf("%lld\n", solve(0, n));      return 0;  }
      
     

 

递推：自底向上的方法，需要注意的是1+5和5+1是一种的，所以要处理一下，从小往大排就不会错了。

#include 
     
        const int MAXN = 8000;  int n, coin[5] = {
   1, 5, 10, 25, 50};  long long dp[MAXN] = {
   1};    int main() {      for (int i = 0; i < 5; i++)          for (int j = 0; j < MAXN - 100; j++)              dp[j + coin[i]] += dp[j];        while (scanf("%d", &n) != EOF)          printf("%lld\n", dp[n]);      return 0;  }
     

 

2018-04-30