动态规划
动态规划满足的全局条件
答案无后效性
- 答案不会随着后面的答案发生改变而改变
最优子结构
- 确定小规模问题的答案后，大问题答案也确定
- 由小问题推出大问题
推出最优子结构的算法流程
观察题目
- 大问题与小问题的联系
状态定义
- 数组的定义
状态转移
- 求出转移方程
边界条件
- 边界处理与初始化
其中最难的是与观察与联系和状态定义，想哭
基础DP
硬币问题
最少硬币问题
思路
int type[] //定义面值数组
int dpmin[] // dpmin[i]表示金额i硬币最少数量；
dpmin[i] = min{dpmin[i], dpmin[i - type[j]] + 1};
练习
http://acm.hdu.edu.cn/showproblem.php?pid=2069 hdu2069
代码如下
#include <cstdio>
#include <iostream>
using namespace std;
const int COIN = 101;
const int MONEY = 251;
int type[5] = {1, 5, 10, 25, 50}; //定义面值数组
int dpmin[251][101]; // dpmin[i]表示金额i硬币最少数量；
// dpmin[i] = min{dpmin[i], dpmin[i - type[j]] + 1};
int ans[251];
void solve() {
dpmin[0][0] = 1;
for (int i = 0; i < 5; i++) {
for (int j = 1; j < COIN; j++) {
for (int k = type[i]; k < MONEY; k++) {
dpmin[k][j] += dpmin[k - type[i]][j - 1];
}
}
}
}
int main() {
int s;
solve();
for (int i = 0; i < MONEY; i++) {
for (int j = 0; j < COIN; j++) {
ans[i] += dpmin[i][j];
}
}
while (cin >> s) {
cout << ans[s] << endl;
}
return 0;
}
经典DP
编辑距离
概念
.编辑距离Edit Distance，又称 Levenshtein.
.两个字串之间，由一个转成另一个所需的最少编辑操作次数.
.编辑操作：
---修改一个字符
---插入一个字符
---删除一个字符
.编辑距离越小，两个串的相似度越大.
例如： S = "ANCF", T = "YNFK";
操作：
---1、把Y改为A;
---2、删掉K;
---3、加入C;
答案为3；
状态定义
dp[i][j] : 表示字符串 S 与 T 的编辑距离；
-dp[0][0] : S 与 T 都为空，编辑距离为0；
-dp[0][j] = j : S 为空，T 长度为 j 的情况，编辑距离为 j , 也就是从 空的 S 添加 j 个字符变成 T 的最小编辑 距离为 j;
-dp[i][j] = i : T 为空，S 长度为 i 的情况，编辑距离为 i , 也就是从 空的 T 添加 i 个字符变成 S 的最小编辑 距离为 i;
