动态规划详解（完结篇）——如何抽象出动态规划算法？以及解题思路

今天直接开始讲解

FIRST：如何抽象出动态规划算法？

这个问题，困扰了无数代OIER，包括本蒟蒻

在比赛的时候，看一道题，怎么想到他是什么算法的呢？

这就需要抽象能力

而不同的算法，往往有着不同的特点

就来说说动态规划的题目特点

1. 通过遍历，能够把所有的情况考虑到。这一点同样适合于递归

2. 有可能存在重叠性的子问题。没错，这一点也适用于递归

有的同学就问了

那动态规划和递归不是同样的特点吗？

回到蒟蒻写的动态规划1

里面说过，动态规划是可以用递归代替的

也就是说，如果你的状态转移方程真的实在绞尽脑汁费劲九牛二虎之力也想不出来，就用递归来做

但代价就是也许拿不到满分

SECOND：解题思路

动态规划抽象出状态之后，就要进行遍历每一个状态

1. 抽象状态

2. 初始化

3. 确定循环起始以及边界

4. 写出状态转移方程

5. 输出

6. return 0;

大概就是上述这个过程了

每日例题：

题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？

输入格式
第一行有 22 个整数 �T（1≤�≤10001≤T≤1000）和 �M（1≤�≤1001≤M≤100），用一个空格隔开，�T 代表总共能够用来采药的时间，�M 代表山洞里的草药的数目。
接下来的 �M 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例
输入 #1复制
70 3 71 100 69 1 1 2
输出 #1复制
3
说明/提示
【数据范围】
对于 30%30% 的数据，�≤10M≤10；
对于全部的数据，�≤100M≤100。

一个纯纯的01背包模板

1. 抽象状态：f[i]表示第i分钟采到的最大价值

2. 初始化：no

3. 确定循环起始以及边界：第一层循环1到m，第二层循环t到0（真的是01背包模板，看不懂的可以借鉴一下上一篇文章）

4. 写出状态转移方程：dp[j]=max(dp[j-w[i]]+val[i], dp[j]);如果采了这个药，那么就要用当前时间减去采药的时间，也就是采药之前需要的时间加上现在的状态

5. 输出（见代码）

真正做题时，大家也可以按照这个顺序，非常的清晰

那么有的同学就要问了：状态定义有什么规律吗？

1. 首先，我们先创建一个数组，f数组，假设他是一维的，然后去想这个一维状态表示什么（简单多了）

2. 就假设是一维，尝试写状态转移方程

3. 如果发现，写不通了，也就是有更多的情况表示不出来

4. 增加维度

然后循环上述操作

但是遇到很难的题，还得是靠智商，因为难的动态规划不仅仅要抽象出来

更需要你优化，也就是减少维度

来迟的AC代码：

# include <iostream>
# include <cstdio>
using namespace std;
int w[105], val[105];
int dp[1005];
int main(){int t,m;    scanf("%d%d",&t,&m);for(int i=1;i<=m;i++){scanf("%d%d",&w[i],&val[i]);}for(int i=1;i<=m;i++) {for(int j=t;j>=0;j--) {if(j>=w[i]){dp[j]=max(dp[j-w[i]]+val[i], dp[j]);}}}    printf("%d",dp[t]);return 0;
}

---

这会动态规划系列就真的结束了

这次讲算法比之前真的费了更大的力气，更多的时间，更多的键盘（）

所以希望各位佬能够点个免费的赞

如果动态规划方面还有什么不明白的，随时私信我

我可以出番外篇（）

这篇文章到这里就结束了

再见