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

今天直接开始讲解

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

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

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

这就需要抽象能力

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

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

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

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

有的同学就问了

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

回到蒟蒻写的动态规划1

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

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

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

second：解题思路

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

抽象状态

初始化

确定循环起始以及边界

写出状态转移方程

输出

return 0;

大概就是上述这个过程了

每日例题：

一个纯纯的01背包模板

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

初始化：no

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

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

输出（见代码）

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

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

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

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

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

增加维度

然后循环上述操作

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

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

来迟的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;
}

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

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

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

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

我可以出番外篇（）

这篇文章到这里就结束了

再见