DP动态规划的基本手段及如何解决问题
1. 那带一个问题，只要解决几个对应的小一点规模的问题就能得到问题本身的解
2. 设计一张表格，每一个格子都是一个问题的解
3. 一步步完成这张表格，根据一个数据，往表格前面的数据查找
4. 获得问题本身的答案
B3635 硬币问题
题面
题目描述
今有面值为 1、5、11 元的硬币各无限枚。
想要凑出 n 元，问需要的最少硬币数量。
输入格式
仅一行，一个正整数 n。
输出格式
仅一行，一个正整数，表示需要的硬币个数。
输入输出样例
输入 #1
15
输出 #1
3
输入 #2
12
输出 #2
2
说明/提示
样例解释
对于样例数据 1，最佳方案是 15=5+5+5，使用到 3 枚硬币。
对于样例数据 2，最佳方案是 12=11+1，使用到 2 枚硬币。
题解
根据题目中的解释，使用贪心或者暴力的方法是肯定写不出正解的。因此模拟一下如果需要凑15枚硬币，那么如果第一次选择
面值为1枚的硬币：还需要凑14枚
面值为5枚的硬币：还需要凑10枚
面值为11枚的硬币：还需要凑4枚
可推算出递推公式，只要计算出当前i的三个面值选项中的min，需要的最小硬币树，继续递归，不断更新f[i]直到i递归到n。
递推公式：
需要注意的是当考虑面值为5或11是需要判断当前需要的硬币是否大于5或11，否则会越界并且不能使用对应面值的硬币。
这就是一个减小规模的过程，就成为动态规划，用一些小的问题解决一个大的问题
代码
#include<iostream>
using namespace std;
int f[10000010]; // 定义 f 数组
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
f[i] = f[i-1] + 1; // i-1 元的方案数，外加一枚 1 元。
if(i>=5) // 考察 i-5 元外加一枚 5 元是否更优
f[i] = min(f[i], f[i-5]+1);
if(i>=11) // 考察 i-11 元外加一枚 11 元是否更优
f[i] = min(f[i],f[i-11]+1);
}
cout << f[n] << endl; // 输出答案，n 元最少几枚
return 0;
}B3636 文字工作
题面
题目描述
机器猫要在电脑前打字。一共需要打 n 个字，但现在文档里只有一个字。
机器猫有两种操作可以做。假设现在已经有 x 个字，机器猫可以选择：
- 往文档最后加一个字。字数变成 x+1。
- 把文档复制粘贴一遍。字数变成 2x。
问机器猫至少需要多少次操作，才能得到恰好 n 个字。
输入格式
仅一行，一个正整数 n。
输出格式
仅一行，一个正整数，表示最少操作次数。
输入输出样例
输入 #1
16
输出 #1
4
输入 #2
5
输出 #2
3
说明/提示
样例解释
样例数据1，1→2→4→8→16，共 4 步。
样例数据2，1→2→4→5，共 3 步。
题解
代码
#include <bits/stdc++.h>
using namespace std;
int f[1000005];
int main() {
int n;
cin >> n;
for(int i=2; i<=n; i++) {
f[i] = f[i-1] + 1; // 方案 1
if(i%2==0) // 如果它可能是方案 2
f[i] = min(f[i], f[i/2] + 1); // 方案 2
}
cout << f[n] << endl;
return 0;
}
