正文请跳过下面这一段
上一篇文章刚写完三天，这个数据太给力了
所以马不停蹄的更新第二期
文章来源地址https://uudwc.com/A/MxwNx
文章来源：https://uudwc.com/A/MxwNx
正文开始
上篇文章，主要讲解的是动态规划的基础概念，未涉及到任何代码
所以基础概念还不太清楚的
戳我
今天会涉及到一些简简单单的代码，以及一些代码方面的知识
上次说过，每个步骤叫做状态，而每个状态也要求最优解
所以我们要用一个数组，来表示我们目前为止每一步的最优状态
注意！！ 表示的是目前为止的，而不是最后的最优解
为什么呢？
因为每个状态有可能被考虑多次，如果a状态第二次考虑比第一次更优，那么就会发生替换
因为动态规划的缩写是dp
所以这个数组一般命名为dp
或者f，标准的状态数组
数组定义完了，现在就是要考虑状态了
有的状态只和一个数有关，有的和两个、三个等等等
听不懂……（小声念叨）
没事 来一个祖传栗子
就以斐波那契数列为例
每一个数都是前面一个数的最优解和前面两个数的最优解的和
也就是f[i]=f[i-1]+f[i-2]
上面这个东西就叫
状态转移方程，大家先记住这个名字，本篇文章后面会涉及到
因为i代表的是这个数是第几个，而表示第i个数的状态的数组是f
在这个例子中，就只和一个数有关，那就是i，f数组就是我们口中的一维数组
如果和两个数有关呢？
假如有n个人，分m份物品，每个人拿第i份物品会增加ci个价值点
这里就需要i和j两个数了
第i个人拿第j个物品的最大价值
因为是蒟蒻瞎说的题，所以状态转移方程写不出来很难写
动态规划三巨头：状态定义，初始化，状态转移方程
也被称作动态规划三要素，在我往期的动态规划文章都说过
状态定义
也就是上面说的f[i]或者f[i][j]
所谓的状态定义就是定义f[i]或者f[i][j]代表的是什么状态。第i个人？第i个牛棚？第i个物品？……
初始化
尽人皆知，c++全局变量默认全部为0
假如要求损失最小值，那么就得用min
一般是min(当前状态，要被转移过来的状态）
这里有两个点要讲：
因为用的是min所以只要被转移状态大于0，当前状态就会不变，还是默认值0
为什么还要min一下当前状态呢？还是因为子问题重叠性这个特性，如果a被考虑两次，就要和被转移状态做一个抉择
浅浅来个例题罢：
题目描述
用递归函数输出斐波那契数列第n项。1，1，2，3，5，8，13……
输入
一个正整数n,表示第n项。
输出
第n项是多少。
样例输入1
3
样例输出1
2
状态定义：f[i]代表第i个数的值
初始化：f[1]=f[2]=1;
状态转移方程：f[i]=f[i-1]+f[i-2]
# include <iostream>
# include <cstdio>
using namespace std;
# define int long long
int n;
int f[1005];
signed main(){
scanf("%lld",&n);
f[1]=f[2]=1;
for (int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
printf("%lld",f[n]);
return 0;
}
今天的讲解到此结束！
动态规划详解系列也将结束
还想看什么算法私信我
