蓝桥杯备赛 Day15 动态规划
动态规划两要素
1.状态
2.状态转移方程
动态规划两性质
1.最优子结构
2.无后效性
状态f[i] 支付i元时所消耗的最小硬币数
状态转移方程推导过程：
f[15]=min{f[14],f[10],f[4]}+1
1.先选1元的,f[15]=f[14]+1=5
2.先选5元的,f[15]=f[10]+1=3
3.先选11元的,f[15]=f[4]+1=5
状态转移方程
f[i]=min{f[i-1],f[i-5],f[i-11]}+1
#include<iostream>
using namespace std;
/*
硬币面值：1, 5, 11。
求支付w元时所消耗的最小硬币数
举例：凑出金额 15。
贪心策略：15 = 11 + 4*1，共使用 5 枚硬币。
动态规划：15 = 5 + 5 + 5，共使用 3 枚硬币。
说明：贪心策略在某些情况下可能无法得到最优解，贪心具有后效性。
*/
/*
状态 dp[i]，支付i元时所需要的最少硬币数
状态转移方程 dp[i]=min{dp[i-1],dp[i-5],dp[i-11]}+1
*/
const int N = 1e2 + 10;
int dp[N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int minx = 0x3f3f3f3f;
if (i >= 1) minx= min(minx,dp[i - 1]) ;
if (i >= 5) minx = min(minx, dp[i - 5]);
if (i >= 11) minx = min(minx, dp[i - 11]);
dp[i] = minx + 1;
//打印dp表（检查每一个阶段对应的状态）
printf("dp[%d]=%d\n", i, dp[i]);
}
return 0;
}