题意：在无限硬币的情况下能组成200的方案数有多少个
思路：DP，设数组 dp[ n ] [ k ] 代表前 n 种硬币能够组成 k 元的方案数，那么就能得到 dp [ n ] [ k ] = dp [ n - 1 ] [ k ] + dp [ n ] [ k - money[ n ] ] ，可以看出当前方案数是全部来源于之前的方案数的，那么可以用滚动数组进行降维，得到状态转移方程 dp [ j ] = dp [ j ]（ 因为滚动数值仍然保留上一次的值，所以这个 dp [ j ] 相当于 dp [ n - 1 ] [ j ] ） + dp [ j - money [ i ] ]
/************************************************************************* > File Name: euler031.c > Author: WArobot > Blog: http://www.cnblogs.com/WArobot/ > Created Time: 2017年06月25日 星期日 15时10分45秒 ************************************************************************/#include#include #define MAX_N 201int32_t main() { int32_t money[8] = { 1 , 2 , 5 , 10 , 20 , 50 , 100 , 200}; int32_t dp[ MAX_N ]; for(int32_t j = 0 ; j < MAX_N ; j++) dp[j] = 1; for(int32_t i = 1 ; i < 8 ; i++){ for(int32_t j = money[i] ; j < MAX_N ; j++){ dp[j] += dp[ j - money[i] ]; } } printf("%d\n",dp[200]); return 0;}