【零基础学懂算法】：动态规划算法
前言：本系列文章旨在介绍笔试题中常见的算法，面向算法零基础小白，以最简单直白的语言方便你更快的理解算法原理和使用方法。
目录
一.算法思想与原理
动态规划算法（dp算法）的核心思想是将复杂问题分解为更小的子问题，通过记忆化（缓存）来避免重复计算，从而提高效率。
这里的记忆化（缓存）是该算法的精髓，就拿斐波那契数列在说，假如我们要求得第8个位置的斐波那契数，那我们就需要提前知道第7个和第6个位置的数，即在计算当前结果的时候我们还需要使用之前计算的结果，而通过记忆化的处理我们将之前计算的结果存储到一定的数据结构中，再后面需要用到这个结果的时候直接将其取出来，这样就避免了重复计算带来的性能损耗。
动态规划算法主要用于解决具有 重叠子问题 和 最优子结构 的问题。
重叠子问题：在问题求解过程中，子问题会被多次重复计算。通过记忆化或填表的方法，可以避免重复计算。
例如，在计算斐波那契数列时，fib(n) 的计算依赖于 fib(n-1) 和 fib(n-2)，而 fib(n-1) 又依赖于 fib(n-2) 和 fib(n-3)，这样很多子问题会被重复计算。
最优子结构：问题的最优解可以由其子问题的最优解来构建。换句话说，解决整个问题的最优解是通过组合解决子问题的最优解来得到的。
例如，在最短路径问题中，从某个节点到目标节点的最短路径可以通过该节点的相邻节点到目标节点的最短路径来得到。
在网上我看到很多文章都是直接上来就大刀阔斧的定义状态、定义状态转移方程......
我感觉这样的讲解非常的不适合小白，因此本篇文章的目的就是从零基础开始先把基础的概念搞明白再讲解算法原理和使用，在动态规划算法中有以下俩个最关键名称需要理解：
1. 什么是状态？
所谓状态指的就是问题在某一特定时刻的子问题的解，每一个状态表示了我们所关心的一个小规模子问题的解，它们共同构成了原问题的解。
例如，如果问题是计算斐波那契数列，假如我们用数组dp[ ]来记录每一位下标对应的斐波那契数，对于dp[ i ]就表示了第 i 个斐波那契数，由于每一位的斐波那契数就是我们要求的子问题的解，那么这里的dp[ i ]就是我们所说的状态。
2. 什么是状态转移方程？
状态转移方程是描述当前状态与之前状态之间关系的公式。它是动态规划算法的核心，通过递推关系推导出问题的最终解。
还是拿斐波那契数列来说，以下图百度百科的解释中我们也可以看见斐波那契数列的定义：F(n)=F(n - 1)+F(n - 2)，而这个式子恰好就诠释了斐波那契数列中不同位置的数的关系，F(n)=F(n - 1)+F(n - 2)就表示了第n个斐波那契数等于前俩个数之和，
而我们在解释状态的时候也说过，在斐波那契数列中每一位的斐波那契数就是我们要求的子问题的解，也就是状态，即F(n)=dp[ i ]。那么由此我们就可以将F(n) = dp[ i ]带入F(n)=F(n - 1)+F(n - 2)，我们就得到了dp[ i ] = dp[ i-1 ] + dp[ i-2 ]，在这样的式子中，dp[ i ]代表现在的状态，dp[ i-1]和dp[ i-2 ]代表了之前的状态，我们就将当前状态和之前状态联系了起来，这个式子为我们提供了如何从一个状态到下一个状态的方法，故而这就是斐波那契数列求解的状态方程。
理解了状态和状态转移方程，你就已经可以完成大部分的动态规划题目了，所以接下来我们直接上手看看如何完成动态规划算法题目。
二.动态规划做题步骤
在上文中我们理解了状态表示和状态转移方程，而这都是原理部分的知识。在以下部分内容则重点在于做题的时候需要注意的步骤。
在动态规划算法的题目中，普遍可以使用以下的做题步骤：
- 定义状态表示
- 定义状态转移方程
- 初始化
- 计算并填表
- 提取最终结果
初次见到这些名词可能会一脸茫然，但是不用担心，下文笔者就对于这几个步骤做出解释。
状态表示和状态方程该如何定义我们其实在上文的算法原理部分就讲解过了，所以这里就不重复说明了，后文会用一道完整的真题来整体过一遍，所以也不用担心自己的理解不够深刻。
▐ 填表
在这样的步骤中有很重要的一个操作就是填表：
我们知道程序是由算法和数据结构俩部分组成的，在动态规划算法中算法部分自然是不用说，那肯定是选择动态规划算法，因此在这部分题目中，我们需要注意的地方就是数据结构部分，我们一般会设置一个一维数组或者二维数组来存放每一个状态，对于这样的数据结构我们一般称之为表，当我们将这个表填满的时候，我们就可以得到任意一个状态及其结果。
还是拿上文的斐波那契数列举例来说，我们新建一个一维数组dp[ ]，其中每一位代表一个状态，那么当我们把这个dp[ ]数组填满了之后，我们就知道了每一位斐波那契数，如果题目问我们第100个斐波那契数是多少，那我们直接在这个dp[ ]数组中取出dp[100]即可得到答案，因此填满这个数据结构（表）的过程其实就是在求解。
▐ 初始化
通过以上的学习，我们知道了求解动态规划题目本质上就是在填表，为了避免我们填表的时候出现差错，在填表之前我们一般还要进行一步初始化的操作。
还是拿刚才的斐波那契数列来说，我们先梳理一下以我们现在了解的知识点可以完成这个题目吗？
- 我们通过一维数组dp[ ]来作为存放每一个状态的表
- 状态转移方程是dp[ i ] = dp[ i-1 ] + dp[ i-2 ]
- 求解的过程就是填表，因此我们需要将dp[ 1 ]，dp[ 2 ]，dp[ 3 ]，dp[ 4 ] ... ... 依次填入dp数组
我们会发现一上来就出现问题了，按照状态转移方程来说dp[ 1 ] = dp[ 0 ] + dp[ -1 ]，但是这里我们要填的第一个dp[ 1 ]就出现数组越界了，dp[ -1 ]是并不符合语法，在数组中怎么会有 -1 这样的下标呢？
而我们要说的初始化其实就是干的这件事，也就是要保证的就是填表的时候不能出现数组越界。
我们可以在斐波那契数列的定义中找到如下的语句，即第一位是0，第二位是1。
那么在初始化步骤中，我们就需要将dp[ 0 ] = 0并且将dp[ 1 ] = 1。这样就避免了数组越界的问题。
▐ 计算并填表
在这部分其实没什么难点，唯一需要注意的就是填表顺序，我们在填表的时候需要保证所需的状态已经计算过了。
还是拿斐波那契数列求解来说，我们是应该从左往右填表呢？还是应该从右往左填表呢？
我们知道斐波那契的特点就是当前数字是前俩个数字的和，那我们理所当然的肯定是从左往右的顺序填表，先填dp[ 0 ]，再填dp[ 1 ]，再填dp[ 2 ] ... ...。如果是从右往左的话，上来填的第一个dp[ i ]就已经难住我们了，故而理应选择从左往右。
▐ 提取最终结果
这一步也很简单，根据题目需求，假如题目要的是第100个斐波那契数，那我们从状态表中拿出dp[ 100 ]返回即可。
以上便是做动态规划算法的几大要点步骤，阅读完了后你可能还不是那么的明确，没关系，下面我们用一道真题来整体完整的疏通一遍。
三.LeetCode力扣完整解题流程
本题选自力扣网，有兴趣的可以自行点击挑战，题目链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）
题目信息：
这道题目和我们讲解算法原理和步骤的斐波那契很像，因此很适合初学者学习。
题目分析
首先，在这个题目中我们可以看到在求解一个问题的过程中，需要利用到其子问题的解，因此我们选择使用动态规划算法，那我们就按照动态规划算法的几大步骤开始做题：
- 定义状态表示：题目题目要求很明显，求得第n个数T(n)，那么我们就用dp[ i ] 表⽰：第 i 个泰波那契数的值。
- 定义状态转移方程：根据题目给出的递推公式 Tn+3 = Tn + Tn+1 + Tn+2，再加上我们第一步确定的状态表示dp[ i ]=T(n)，我们可以得到状态转移方程：dp[ i ] = dp[ i - 1] + dp[ i - 2 ] + dp[ i - 3 ]
- 初始化：题目要求返回第n个数，也就是dp[ n ]的元素，那么我们就需要初始化一个大小为n+1的数组（如果是大小为n的数组的话只能访问到dp[ n-1 ]的位置，因为数组是从0下标开始的）。同时题目给出了T0 = 0, T1 = 1, T2 = 1的信息，这也是我们需要初始化的部分，状态表示dp[ i ]=T(n)可以得到即dp[ 0 ]=0，dp[ 1 ]=1，dp[ 2 ]=1。
- 计算并填表：使用for循环从3开始往数组里面填数据即可（因为0，1，2位置的数据我们已经初始化过了）。填表的顺序肯定是从左往右，从小到大的顺序。
- 提取最终返回结果：返回dp[ n ]即可
完整代码
class Solution {
public int tribonacci(int n) {
//1.确定状态表示dp[i]=Tn
//2.确定状态转移方程dp[ i ] = dp[ i - 1] + dp[ i - 2 ] + dp[ i - 3 ]
//3.初始化
if(n == 0) {//直接返回初始值
return 0;
}else if(n == 1 || n == 2) {//直接返回初始值
return 1;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
//4.填表
for(int i=3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
//5.返回结果
return dp[n];
}
}对于以下部分内容，都是属于对于该题目算法的优化，如果是初学者的话，不建议继续阅读，重点应该放在掌握动态规划算法本身。
使用滚动数组进行优化
我们可以发现在求某个位置的值的时候其实只需要用前面俩位即可，比如求i=3的时候，其实只需要用i=0 i=1 i =2这三个数，同理求i=4和5的时候也一样，因此我们可以使用一个大小为3的滚动数组来实现优化，将一维数组优化为由3个变量组成的滚动数组。
完整代码
class Solution {
public int tribonacci(int n) {
//1.确定状态表示dp[i]=Tn
//2.确定状态转移方程dp[ i ] = dp[ i - 1] + dp[ i - 2 ] + dp[ i - 3 ]
//3.初始化
if(n == 0) {//直接返回初始值
return 0;
}else if(n == 1 || n == 2) {//直接返回初始值
return 1;
}
//4.填表
//用a,b,c组成滚动数组
int a = 0;//相当于dp[0]
int b = 1;//相当于dp[1]
int c = 1;//相当于dp[2]
int ret = 0;//用于存储最终结果
for(int i=3; i <= n; i++) {
ret = a + b + c;
a = b;//a走到b的位置
b = c;//b走到c的位置
c = ret;//c再往后走一步
}
//5.返回结果
return ret;
}
}这样优化后的空间复杂度就从原来的O(n)变为了O(1)
本次的分享就到此为止了，希望我的分享能给您带来帮助，创作不易也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！
如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！
有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见
原文地址：https://blog.csdn.net/m0_69519887/article/details/142690878
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！