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;
}

BFS

#include<bits/stdc++.h>
using namespace std;
struct s{
    int a,b;//a是当前钱数，b是用了几个阴币
};
int n,ans,vis[int(1e6+5)];//防止MLE && TLE
queue<s> q;
int main(){
    cin>>n;
    q.push({0,0});
    while(q.size()){
        ans++;
        int a=q.front().a,b=q.front().b;
        q.pop();
        if(a==n){
            cout<<b;
            return 0;
        }
        vis[a]=1;
        if(a+11<=n && !vis[a+11]){
            vis[a+11]=1;
            q.push({a+11,b+1});
        }
        if(a+1<=n && !vis[a+1]){
            vis[a+1]=1;
            q.push({a+1,b+1});
        }
        if(a+5<=n && !vis[a+5]){
            vis[a+5]=1;
            q.push({a+5,b+1});
        }
    }
    return 0;
}