千锤百炼算法系列之动态规划
赞
踩
题外话
这段时间,我必须把算法弄明白
这篇直接讲解动态规划所有细节!
前面那篇
也有关于动态规划的讲解,也非常详细
很简单,我成尊不就是了?!!!
正题
动态规划
这里我们主要是让大家明白什么是动态规划,怎么用动态规划解题
我就不用那些官方的东西了
让我们直接上例题!!
第n个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
先说一下动态规划的步骤
动态规划步骤
1.动态表示
我们所用的动态表示不同,进行下面步骤的时候也会有一些区别
一道题可能有多种动态表示,也有可能只有一种
什么是动态表示呢?
就是我们根据题目信息所找到的dp[i]
像这道题我们可以设置dp[i]为第i个位置的泰波那契值
2.动态转移公式
动态转移公式是根据动态表示和题目信息所得到的
所以动态表示不同,我们的动态哦转移公式肯定是不同的
那么动态转移公式是什么呢?
就是dp[i]等于从题目信息中提取出的信息所建立的公式
咱们这道题比较简单,动态转移公式相当于直接在题目中给出了
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
这很显而易见吧,相信大家都能理解嗷
3.初始化
①我们有了动态转移公式,但是我们没有值
我们需要从dp[0],dp[1],dp[2]一直算到dp[n],也就是从左到右的顺序
我们如果想求dp[3]的话是不是需要知道dp[0],dp[1],dp[2],它们三个的值
但是我们根本没有它们三个的值,所以这个时候就需要根据题干信息,然后将我们公式的起始点dp[0],dp[1],dp[2]进行初始化赋值
②除此之外,我们需要给i规定一个范围,大家想想
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
这个公式中,i可以等于0吗?
很显然不可以,数组越界了
我们需要从i=3开始
4.填表顺序
填表顺序自然是从左到右,从头到尾计算
5.返回值
根据题干要求找到正确的返回值
我们要求第n个泰波那契值
那么根据我们设立的动态表示
返回值就是dp[n]
代码详解
public int test01(int n) {
//我们i从3开始,我们需要处理一下,n=0,1,2的情况
if (n==0)
{
return 0;
}
if (n==1||n==2)
{
return 1;
}
//1.创建动态表示
//我们要求dp[n],那么就应该有n+1个元素
int[] dp=new int[n+1];
//2.创建动态转移方程
//3.初始化
//4.填表顺序
dp[0]=0;
dp[1]=1;
dp[2]=1;
for (int i = 3; i <=n; i++) {
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
return dp[n];
}
空间优化(滚动数组)
我们这道题其实还可以空间优化一下
根据动态转移公式dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
我们只需要四个变量,就可以完成这个操作
如下图
代码详解
//我们i从3开始,我们需要处理一下,n=0,1,2的情况
if (n==0)
{
return 0;
}
if (n==1||n==2)
{
return 1;
}
//直接初始化a,b,c,d
int a=0;
int b=1;
int c=1;
int d=0;
for (int i = 3; i <=n; i++) {
d=a+b+c;
//计算完d的值,将b赋值给a,c赋值给b,d赋值给c
a=b;
b=c;
c=d;
}
return d;
}
小结
落魄谷中寒风吹
春秋蝉鸣少年归
荡魂山处石人泪
定仙游走魔向北
逆流河上万仙退
爱情不敌坚持泪
宿命天成命中败
仙尊悔而我不悔
继续学习去了!
麻烦家人们一键三连!!!(点赞,关注,收藏!!!)
