DP 入门题

题意

有面值 1，5，11 的三种硬币，求付 $n$ 元钱硬币数量最少

思路

第 $i$ 元钱时，可以：

• 5 张 1 元换成 1 张 5 元
• 11 张 1 元换成 1 张 11 元

然后取硬币数最少的选项加 1

代码（DP）

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		if (i < 5){	// 钱数小于 5
			a[i] = a[i - 1] + 1;
		}else if (i < 11){	// 钱数大于 5，小于 11
			a[i] = min(a[i - 1],a[i - 5]) + 1;
		}else{	// 钱数大于 11
			a[i] = min({a[i - 1],a[i - 5],a[i - 11]}) + 1;
		}
	}
	cout << a[n];
	return 0;
}

代码（DFS）

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int dfs(int n){
    if (a[n])   return a[n];
	if (n <= 0)	return a[n] = 0;
	else if (n == 1){
		return a[n] = 1;
	}else if(n < 5){
		return a[n] = dfs(n - 1) + 1;
	}else if (n < 11){
		return a[n] = min(dfs(n - 5),dfs(n - 1)) + 1;
	}
	return a[n] = min({dfs(n - 5),dfs(n - 1),dfs(n - 11)}) + 1;
}
int main(){
	int n;
	cin >>n;
	cout << dfs(n);
	return 0;
}