输入一行,包含一个整数n
1 <= n <= 200
set<int>paths_hash;
int path[3];
int money[3]= {1,2,5};
void DFS(int u) {
if(u==0) {
paths_hash.insert(path[0]*200*200+path[1]*200+path[2]);
} else if (u<0) return;
else {
for(int i=0; i<3; i++) {
path[i]++;
DFS(u-money[i]);
path[i]--;
}
}
}
//递归DFS搜索算法的时间复杂度太高,不可行。使用动态规划可以大大降低时间复杂度。
int change(int n) {
int dp[n+1][3];
int sum;
for(int i=0; i<=n; i++) dp[i][0]=1;
for(int i=0; i<=n; i++) {
for(int j=1; j<3; j++) {
sum=0;
for(int k=0; i-k*money[j]>=0; k++) {
sum+=dp[i-k*money[j]][j-1];
}
dp[i][j]=sum;
}
}
return dp[n][2];
}