千锤百炼算法系列之动态规划

题外话

这段时间,我必须把算法弄明白

这篇直接讲解动态规划所有细节!

前面那篇

千锤百炼之每日算法(一)-CSDN博客

也有关于动态规划的讲解,也非常详细

很简单,我成尊不就是了?!!!

正题

动态规划

这里我们主要是让大家明白什么是动态规划,怎么用动态规划解题

我就不用那些官方的东西了

让我们直接上例题!!

第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;
}