【算法模板】动态规划，不可多得的干货

================================================================================

📒博客首页：铁甲小宝同学 📒

🌞文章目的：动态规划基础篇分享🌞

🙏博主也在学习阶段，如若发现问题，请告知，非常感谢🙏

💗同时也非常感谢各位小伙伴们的支持💗

🌈每日一语：你相信光吗？ 🌈

将过去和羁绊全部丢弃，不好吝惜那为梦想留下的泪水 。 ——路飞

文章目录

• 【算法模板】动态规划（基础DP篇）

• • 前言

• 什么是动态规划？

• 动态规划的做题方法

• 一维DP

• • 简介

• 走进一维DP

• 模块练习题

• 二维DP

• • 简介

• 走进二维DP

• 模块练习题

• 总结

前言

博主因最近刷的大部分都是动态规划的算法题，所以也把博主所刷的心得和习题在本篇文章中总结分享给大家，并且希望能帮助到大家。

感谢： 感谢csdn、力扣、代码随想录等平台和大佬们提供的习题和题解！！

什么是动态规划？

动态规划 （英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题。（百度百科得到的答案）

简单的就是说：用简单的方法来解决复杂的问题！

核心思想：

动态规划的核心就是 有记忆，减少不必要的计算！

动态规划的做题方法

一般我们在做动态规划这种题的时候一般会有一下这几个步骤：

• 定义一个的dp数组。

• dp数组的初始化。

• 列举动态规划推导公式。

• 进行循环遍历逐步改变dp数组的值，直道循环结束能获取我们所需要的值即可。

我们只要上述的几个步骤没有出现什么问题的话，那么这个这个题也就是手到擒拿了！

而上述步骤中比较难的就是 动态规划推导公式 的推导，一般在做题时我们很容易的知道这个题是用动态规划来解决这个问题。但是每次就会卡到动态规划推导公式这个地方（不要问我为什么5555）。所以这个也是我们需要提高的地方！！！

给大家一些 建议 ，在做动态规划题的时候 一定要自己推导自己的动态规划推导公式 ，就算写不出来我们在看题解的时候也可以那我们自己推导出来的公式和官方的公式进行一个对比，每次在做题的时候只要能保证这点，则以后的进步就会越来越大！！！

一维DP

简介

在上面我们已经知道了什么是 DP 了，那么什么又是 一维DP 呢？

一维DP：

通常的讲 一维DP 就是通过一维的数组来满足 推导公式 的一个求解。

int[] dp = new int[10];//则表示创建了一个长度为10的一维DP数组。

//例如：推导公式

dp[i] = max(dp[i - 2] + dp[i - 1] , dp[i])//这个就是一个比较简单的一维DP推导公式！

走进一维DP

上述中我们知道了什么是 一维DP ，那我们就要来走进这个它，并且征服它！同学们来看下面的例题吧。

例题：

509. 斐波那契数

题目：

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

示例：

输入：n = 2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

做题步骤：

还记得我们第一步需要怎么来分析的吗？

第一步我们需要确定这题的 DP 数组该怎么去创建？

第二步需要我们推导出本题的 DP 公式。

第三步进行循环得到我们需要的结果。

思路：

通过做题步骤我们能知道这个 DP数组 的长度是 n + 1 （因为需要从0开始到n，所以长度也就是 n + 1 ）

题目所说从 1 后面开始每一项的数字都是前两项的和。通过解析这句话我们能知道我们的 循环是从2开始，到n结束 。而推导公式则就是：

dp[i] = dp[i - 1] + dp[i - 2]

当我们完成上述的步骤时接下来就是将这题给实现了。

代码：

Python版本：

class Solution:

def fib(self, n: int) -> int:

if n < 2:

return n

dp = [0]* (n + 1)

dp[1] = 1

for i in range(2 , n + 1):

dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

Java版本：

class Solution {

public int fib(int n) {

if (n == 0) return 0;

if (n == 1) return 1;

int[] dp = new int[n + 1];

dp[1] = 1;

for (int i = 2; i < n + 1; i++){

dp[i] = dp[i - 1] + dp[i - 2];

}

return dp[n];

}

}

我们做了一个比较简单的DP题，那我们再来看另外一个简单的DP问题吧

题目：

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例：

输入：cost = [10,15,20]

输出：15

解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。

总花费为 15

做题步骤：

最后

不知道你们用的什么环境，我一般都是用的Python3.6环境和pycharm解释器，没有软件，或者没有资料，没人解答问题，都可以免费领取（包括今天的代码），过几天我还会做个视频教程出来，有需要也可以领取~

给大家准备的学习资料包括但不限于：

Python 环境、pycharm编辑器/永久激活/翻译插件

python 零基础视频教程

Python 界面开发实战教程

Python 爬虫实战教程

Python 数据分析实战教程

python 游戏开发实战教程

Python 电子书100本

Python 学习路线规划

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Python工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Python爬虫全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注：python）

zZG4ubmV0L2ZlaTM0Nzc5NTc5MA==,size_16,color_FFFFFF,t_70)

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Python工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Python爬虫全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注：python）
[外链图片转存中…(img-29f1FhSB-1711207957181)]文章来源地址https://www.toymoban.com/news/detail-857042.html

到了这里，关于【算法模板】动态规划，不可多得的干货的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！