动态规划详解(2)——初见代码

正文请跳过下面这一段

上一篇文章刚写完三天,这个数据太给力了

所以马不停蹄的更新第二期

文章来源地址https://www.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个物品的最大价值

因为是蒟蒻瞎说的题,所以状态转移方程写不出来很难写

动态规划三巨头:状态定义,初始化,状态转移方程

也被称作动态规划三要素,在我往期的动态规划文章都说过

  1. 状态定义

也就是上面说的f[i]或者f[i][j]

所谓的状态定义就是定义f[i]或者f[i][j]代表的是什么状态。第i个人?第i个牛棚?第i个物品?……

  1. 初始化

尽人皆知,c++全局变量默认全部为0

假如要求损失最小值,那么就得用min

一般是min(当前状态,要被转移过来的状态)

这里有两个点要讲:

  1. 因为用的是min所以只要被转移状态大于0,当前状态就会不变,还是默认值0

  1. 为什么还要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;
}

今天的讲解到此结束!

动态规划详解系列也将结束

还想看什么算法私信我

感谢观看

原文地址:https://blog.csdn.net/lsy201009/article/details/128904550

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月15日 01:51
如何安装多个版本的python,python可以装两个版本吗
下一篇 2023年09月15日 01:58