(记忆化搜索) $O(2^v)$
- 定义状态,(剩下需要凑的钱, 目前正在考虑的货币面值);
- 计算状态,考虑当前使用该面值货币或者使用该面值货币;详见代码
时间复杂度
每次考虑一个面值都有使用或者不使用两种情况,一共有v种货币所以_粗略_计算时间复杂度是$O(2^v)$,但同一种货币可以使用无数次直到超出目标价值,所以时间复杂度应当和目标$n$有关,根据状态转移,时间复杂度的计算是$f(n, i) = f(n-a[i], i) + f(n, i+1), n>0$.详细推复杂度请y总指导(溜了
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e4+1;
int a[26], mem[maxn][26];
int n, re, V;
int dfs(int remain, int cur){
if(cur == V) return 0;
if(remain < 0) return 0;
if(remain == 0) return 1;
auto& v = mem[remain][cur];
if(v != -1) return v;
int cnt = 0;
// pick cur
cnt += dfs(remain - a[cur], cur);
// not pick cur
cnt += dfs(remain, cur+1);
return v = cnt;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> V >> n;
for(int i = 0; i < V; ++i) cin >> a[i];
memset(mem, -1, sizeof mem);
re = dfs(n, 0);
cout << re << "\n";
}