动态规划

动态规划两要素
1.状态
2.状态转移方程
动态规划两性子
1.最优子布局
2.无后效性

状态f 付出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=min{f[i-1],f[i-5],f[i-11]}+1

2. #include<iostream>
3. using namespace std;
5. /*
6. 硬币面值：1, 5, 11。
7. 求支付w元时所消耗的最小硬币数
8. 举例：凑出金额 15。
9. 贪心策略：15 = 11 + 4*1，共使用 5 枚硬币。
10. 动态规划：15 = 5 + 5 + 5，共使用 3 枚硬币。
11. 说明：贪心策略在某些情况下可能无法得到最优解，贪心具有后效性。
12. */
14. /*
15. 状态 dp[i]，支付i元时所需要的最少硬币数
16. 状态转移方程 dp[i]=min{dp[i-1],dp[i-5],dp[i-11]}+1
17. */
19. const int N = 1e2 + 10;
20. int dp[N];
21. int main() {
23.         int n; cin >> n;
24.         for (int i = 1; i <= n; i++) {
25.                 int minx = 0x3f3f3f3f;
26.                 if (i >= 1) minx= min(minx,dp[i - 1]) ;
27.                 if (i >= 5) minx = min(minx, dp[i - 5]);
28.                 if (i >= 11) minx = min(minx, dp[i - 11]);
29.                 dp[i] = minx + 1;
30.                 //打印dp表（检查每一个阶段对应的状态）
31.                 printf("dp[%d]=%d\n", i, dp[i]);
32.         }
33.        
34.         return 0;
35. }

复制代码