上饶做网站多少钱,网站搭建价格表,湖南省建设厅官方网站,网站开发流程中网站制作包括文章目录 一、前言二、动态规划理论基础1、基本概念2、动态规划五部曲【✔】3、出错了如何排查#xff1f; 三、实战演练#x1f5e1;0x00 斐波那契数0x01 第N个泰波那契数0x02 爬楼梯0x03 三步问题0x04 使用最小花费爬楼梯⭐解法一解法二 0x05 解码方法* 四、总结与提炼 一、… 文章目录 一、前言二、动态规划理论基础1、基本概念2、动态规划五部曲【✔】3、出错了如何排查 三、实战演练0x00 斐波那契数0x01 第N个泰波那契数0x02 爬楼梯0x03 三步问题0x04 使用最小花费爬楼梯⭐解法一解法二 0x05 解码方法* 四、总结与提炼 一、前言 本文要为大家带来的是dp动态规划相信这是令很多同学头疼的一个东西也是在大厂面试中很喜欢考的一个经典算法 本文总共会通过四道题来逐步从浅至深地带读者逐步认识dp动态规划
二、动态规划理论基础 首先在讲解题目之前我们要先来说说动态规划理论基础让大家知道到底什么是【动态规划】 1、基本概念
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。如果读者有学习过【贪心算法】的话就可以知道其和动态规划是很类似的但是呢却有着本质的区别对于 贪心 而言是 局部直接选最优但是对于 动规 而言则是 通过上一个状态去推导出下一个状态 例如有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大 本题若是使用 动态规划 来做需要先表示出数组dp的状态通过dp[j-weight[i]]推导出dp[j]然后得出 状态转移方程max(dp[j], dp[j - weight[i]] value[i])才能计算出最终的结果但若是使用 贪心算法 来求解的话直接在每次拿物品选一个最大的或者最小的就完事了 所以大家在做题的时候只要牢牢记住它们而言的最本质区别即可题目刷多了自然也就很好区分
2、动态规划五部曲【✔】 清楚了动态规划的基本概念后我们再来看看在解决动态规划的问题时的解题步骤 做动规题目的时候很多同学会陷入一个误区就是以为把 状态转移公式 背下来照葫芦画瓢改改就开始写代码甚至把题目AC之后都不太清楚dp[i]表示的是什么所以遇到一些同种类的其他题目时就会手足无措状态转移公式递推公式是很重要但动规不仅仅只有递推公式。对于动态规划问题我将拆解为如下五步曲 确定dp数组dp table以及下标的含义确定递推公式状态转移方程dp数组如何初始化确定遍历顺序对dp数组进行填表确认返回值 / 输出内容 一些同学可能想为什么要先确定递推公式然后再考虑初始化呢 因为一些情况是递推公式决定了dp数组要如何初始化
所以我们要先根据dp的状态来推导出状态转移方程接着再通过去分析这个方程然后推敲出dp数组要怎样去做一个初始化才比较合适不会导致越界的问题。所以对于那些只知道记公式但是不知道如何初始化和遍历数组的同学就会显得尴尬
3、出错了如何排查 相信大家在写代码的时候一定会出现各种各样的Bug那要如何去解决呢还记得之前的 LeetCode转VS调试技巧 吗 但是对于动态规划而言就是在力扣中 把dp数组打印出来看看究竟是不是按照自己思路推导的。这是最简洁明了的方式所以我们遇到问题后不要害怕而是要逐步地去分析、排查问题加强自己排查错误的能力如果还是不会了再去请教别人但是在请教之前也先请问问自己下面的三个问题 这道题目我举例推导状态转移公式了么我打印dp数组的日志了么打印出来了dp数组和我想的一样么 把上面三个问题想明白之后再去问别人即经过了自己的思考之后有了自己的见解这样才能更有效果并且做到事半而功倍
三、实战演练 在了解了一些动态规划的基础理论之后我们还是要进入实际的问题 0x00 斐波那契数
原题传送门力扣509.斐波那契数
首先第一道动态规划的入门题必须选择的就是【斐波那契数】下面我会给出三种解法首先是最简单的一种即 递归解法不做详细展开不懂可以看看 C语言函数章节 中的函数递归就会很清楚了
class Solution {
public:int fib(int n) {if(n 2) return n;return fib(n - 1) fib(n - 2);}
};接下去的话就是我们本题的重点即 动态规划 的解法 首先的话就是要去创建dp数组这里使用到的是 CSTL之vector类如果有不懂的同学可以去看看我们初始化出一个大小为n 1的数组
vectorint dp(n 1);接下去我们要去做的就是要去推导出这个 状态表示方程那对于斐波那契数列我们很熟悉后一个数等于前两个数之和而且后面的数依赖于前面的数所以我们的遍历数组也应该是从左向右
dp[i] dp[i - 2] dp[i - 1];再者我们就需要通过上面这个 状态表示方程 来对这个dp数组去做一个初始化的工作此时我们需要去考虑的就是这个越界的问题因为当前的dp[i]依赖的是前两个数所以若此刻的i 0的话前两个数就会发生越界的情况若是i 1第一个数就会发生越界所以 我们要对前两个数做一个初始化的操作 dp[0] 0, dp[1] 1;那在初始化完成之后我们就可以去做遍历填表的工作了因为前两个数字已经被初始化了所以从下标为2的地方开始向后遍历
for(int i 2; i n; i)
{dp[i] dp[i - 2] dp[i - 1];
}当遍历填表结束后因为所求的是第N个斐波那契数所以我们就需要去返回dp[n]
return dp[n];以下即为整体代码展示
class Solution {
public:int fib(int n) {if(n 1) return n;// 1.创建dp表vectorint dp(n 1);// 2.初始化dp[0] 0, dp[1] 1;// 3.遍历填表for(int i 2; i n; i){dp[i] dp[i - 2] dp[i - 1];}// 4.返回值return dp[n];}
};读者可以通过执行结果来看看dp动态规划解法的优势 再下面一种方法则是通过 滚动数组 的形式进行求解 可能读者有所不太理解什么是【滚动数组】如果你了解迭代算法的话就可以知道其实并不复杂。原理也是一样的我们直接通过定义一维数组
int dp[2];然后将上面dp动态规划中的 递推公式 转换成迭代的形式即可
for(int i 2; i n; i)
{sum dp[0] dp[1];// 迭代dp[0] dp[1];dp[1] sum;
}其余的没有大变化代码如下
class Solution {
public:int fib(int n) {if(n 1) return n;int sum 0;int dp[2]; // 一维数组模拟dp[0] 0, dp[1] 1;for(int i 2; i n; i){sum dp[0] dp[1];// 迭代dp[0] dp[1];dp[1] sum;}return dp[1]; // 最后累加的结果存入了dp[1]}
};稍做了一些优化看看运行效率 0x01 第N个泰波那契数
原题传送门力扣1137.第 N 个泰波那契数
看完斐波那契数之后我们再来看一个东西叫做【泰波那契数】不知读者有否听说过呢1、题目解读 首先我们来解读一下本题的意思 相信读者在看到【泰波那契数】的时候不禁会联想到【斐波那契数】它们呢是一对孪生兄弟这个 泰波那契数 相当于是 斐波那契数 的加强版我们首先可以来看到这个递推公式Tn3 Tn Tn1 Tn2读者可能看不太懂我们将其做一个转换为Tn Tn-1 Tn-2 Tn-3即把所有n都统一-3。那么第N个泰波那契数就等于前面3个泰波那契数的和 看到上面的T3就是前3个数的和等于2以此类推T4就是T1 T2 T3 4
2、解题方法 看完了上面对于题目的分析之后下面我将介绍两种解法 ① dp动态规划
首先的话就是本题需要掌握的重点即【动态规划】的解法我们要分成五步去求解
状态表示
首先读者要清楚的是在求解动态规划的题目时都是需要一个dp数组的那么对于【状态表示】的含义就是dp表里的值所表示的含义 那这个状态表示是怎么来的呢 ① 第一个呢就是按照题目要求来即dp[i]表示的就是第i个泰波那契数列的值
② 第二个呢则是需要读者有丰富的刷题经验可以读完题目之后就得出对应的结果
③ 第三个呢则是在分析问题的过程中发现重复的子问题 如果读者之前有接触过类似的动态规划问题的话就会看到一些题解里讲这道题的 状态表示 是怎样的然后就直接讲本题的 状态表示方程根本没有说这道题的状态表示是怎么来的。这个得来的过程我会在其他动态规划的题目中进行讲解 所以读者在解类似的问题时一定要知道下面的这个【状态表示方程】是怎么来的做到 “ 知其然知其所以然 ” 状态表示方程
那么本题的状态表示方程为dp[i] dp[i - 1] dp[i - 2] dp[i - 3]
初始化
在清楚【状态表示方程】该如何写之后我们要去做的就是对这个dp数组做一个初始化的工作。看到下面的这个dp数组如果在一开始我们的下标取值就到0的话那么i - 1、i - 2、i - 3这些就会造成 越界 因此我们要给这个dp数组去做一个初始化具体的就是对前三个数据即dp[0]、dp[1]、dp[2]分别初始化为【0】【1】【1】那我们在后面遍历计算的时候就只需要从下标为3的位置开始即可 dp[0] 0, dp[1] dp[2] 1;填表顺序
接下去的话就是把dp数组按照 状态表示方程 给填充好即可
for(int i 3; i n; i)
{// 状态转移方程dp[i] dp[i - 1] dp[i - 2] dp[i - 3];
}返回值
最后一块我们处理返回值根据题目要求我们是要返回【第 n 个泰波那契数 Tn 的值】所以直接 return dp[n] 即可 但是呢若只考虑上面的这一些在提交的时候是会出现越界的情况因为在题目中给出的n的范围为[0, 37]因此对于dp[0]还好说但对于后面的数据就会出现越界的情况 因此我们还需要去考虑一些边界的问题
// 边界问题处理
if(n 0) return 0;
if(n 1 || n 2) return 1;整体代码会在最后给出
② 迭代优化✔ 看完上面这一种我们再来看看其是否可以去做一个优化 如果读者有接触过迭代算法的话应该很快能想到本题的思路因为是三个三个去做的累加所以我们在这里可以定义三个变量a、b、c它们累加后的值可以放到变量d中 因此在累加完一轮之后我们就需要去做一个迭代的操作
a b; b c; c d;那么在最后我们所需要返回的值就是这个d
return d;3、复杂度
时间复杂度: 对于第一种dp的解法其时间复杂度为 O ( n ) O(n) O(n)而对于第二种迭代的解法时间复杂度为 O ( 1 ) O(1) O(1) 空间复杂度: 对于第一种dp的解法其空间复杂度为 O ( n ) O(n) O(n)而对于第二种迭代的解法时间复杂度为 O ( 1 ) O(1) O(1) 所以就这么对比下来迭代优化的方法还是值得大家去掌握的
4、Code 首先是第一种dp动态规划的解法 class Solution {
public:int tribonacci(int n) {// 边界问题处理if(n 0) return 0;if(n 1 || n 2) return 1;// 1.创建dp表vectorint dp(n 1);// 2.初始化dp[0] 0, dp[1] 1, dp[2] 1;// 3.填表for(int i 3; i n; i){// 状态转移方程dp[i] dp[i - 1] dp[i - 2] dp[i - 3];}// 4.返回值return dp[n];}
};然后的话是第二种利用迭代优化的方法 class Solution {
public:// 空间优化int tribonacci(int n) {// 特殊情况处理if(n 0) return 0;if(n 1 || n 2) return 1;int a 0, b 1, c 1, d 0;for(int i 3; i n; i){d a b c;// 迭代a b; b c; c d;}return d;}
};0x02 爬楼梯
原题传送门力扣70.爬楼梯
我们再来看一道和斐波那契数很像的题目看了代码后你就会有这样的感觉题目意思很简单若是你现在在爬楼梯的话每次只能上1 / 2个台阶请问上到第N个台阶有多少种不同的方法。这个其实也和【青蛙跳台阶】非常得类似不过在那个时候我们是使用 递归 来进行求解的这里我们要考虑使用dp动态规划 不必多解释直接上代码这里唯一要注意的一点就是在初始化的时候是要去初始化dp[1]和dp[2]而不是去初始化dp[0]因为台阶并没有0号台阶而是从1号开始
class Solution {
public:int climbStairs(int n) {if(n 2) return n;vectorint dp(n 1);dp[1] 1; // 从第一层楼梯开始初始化dp[2] 2;for(int i 3; i n; i){dp[i] dp[i - 2] dp[i - 1];}return dp[n];}
};0x03 三步问题
原题传送门面试题0801.三步问题
看完了爬楼梯之后我们再来做一个进阶解决一个三步问题首先来看一下题目所描述的意思刚才我们一次是只能上1阶、2阶现在的话是可以上3阶了那么爬楼梯的种类就会增多 那我们先来分析一下到[1]号台阶有1种方法到[2]号台阶有2种方法分别是1 1和0 2到[3]号台阶则是有1 1 1、0 2 1、0 1 2、0 3可以看做是【1 1 2 4】那么以此类推到达第4号台阶即为【1 2 4 7】 那分析完题目后我们就要根据动规五部曲来完成对题目的分析 首先第一步就是需要去确定状态表示那经过我们的分析本题的dp[i]表示的就是 到达 i 位置时一共有多少种方法 接下去呢我们就需要通过这个i位置的状态以及dp数组的含义去进一步划分思考问题 。那根据题目中来看因为是需要走三步我们从i位置往前推出i - 3、i - 2、i - 1这三个位置 那么从这三个位置到下标为i的位置即为dp[i - 1]、dp[i - 2]、dp[i - 3]很明显我们就可以推出状态转移方程为
dp[i] dp[i - 1] dp[i - 2] dp[i - 3]接下去呢我们就需要去考虑初始化的问题了主要是要考虑到 越界 这一块的问题这个我在讲解前面的题目时也有讲到过因为不存在0号台阶所以当此时的 i 1 的话前面的三个数就会发生越界的问题 那我们就可以对这三个位置去做一个初始化的工作了 接下去我们要来确立的就是填表顺序了上面说到过这个i位置的值依赖于前3个值所 以我们的填表顺序就需要【从左往右】来进行 那么最后的返回值即为dp[n] 根据上面的五部曲我们先来看看代码该如何去进行书写
class Solution {
public:int waysToStep(int n) {// 1.创建dp表vectorint dp(n 1);// 2.初始化dp[1] 1, dp[2] 2, dp[3] 4;// 3.填表for(int i 4; i n; i){dp[i] dp[i - 1] dp[i - 2] dp[i - 3];}// 4.返回值return dp[n];}
};首先第一个问题就是很明显的越界问题反应快的同学应该很快就可以察觉到时前面三个位置的问题 所以我们应该在最前面加上这样的一些判断
// 考虑越界问题
if(n 1 || n 2) return n;
if(n 3) return 4;但是呢在提交之后发现还有错误存在仔细观察的话发现这是一个 运行时异常叫做signed integer overflow —— 有符号数的整数溢出 原题结果可能很大你需要对结果模1000000007 如果读者对题目本身还有印象的话就可以知道本题的结果可能会很大所以题目中讲到要我们去做【取模】的运算
这里我们先去定义一个常量因为对于1000000007它的值的即为1e9 7
// 定义常量
const int MOD 1e9 7;然后在填表遍历的时候就可以去对所计算出来的值做一个取余的操作
dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;以下即为整体的代码展示
class Solution {
public:int waysToStep(int n) {// 定义常量const int MOD 1e9 7;// 考虑越界问题if(n 1 || n 2) return n;if(n 3) return 4;// 1.创建dp表vectorint dp(n 1);// 2.初始化dp[1] 1, dp[2] 2, dp[3] 4;// 3.填表for(int i 4; i n; i){dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;}// 4.返回值return dp[n];}
};然后就看到很顺利地通过了 0x04 使用最小花费爬楼梯⭐
原题传送门746.使用最小花费爬楼梯
知道了怎么去爬楼梯之后我们再来做一个进阶如何利用最小的花费去爬楼梯本题很锻炼大家的dp思维准备好发车了首先我们来分析一下题目的意思就是我们在向上爬楼梯的时候需要去支付一定的费用可以选择从 下标为 0 或下标为 1 的台阶开始爬楼梯题目要我们计算的就是 怎样去爬才可以使得爬到楼顶所需要花费的最少在这里读者尤其要注意的一个点是关注楼顶在哪里仔细看示例就可以发现楼顶应该是在cost[n]的位置才对 解法一 接下去我们就可以开始通过一步一步地去进行求解 首先还是一样我们要去定义dp数组并且了解这个dp[i]所表示的含义是什么即到达i位置时的最小花费 接下去呢我们就要通过当前的这个i的位置之前或者之后的状态去推导出【状态转移方程】来表示dp[i] 因为我们可以选择向上爬一个或者两个台阶所以就将求解dp[i]转换为了两个子问题 先到达 i - 1 位置然后支付 cost[i - 1]走一步先到达 i - 2 位置然后支付 cost[i - 2]走二步 可以看到因为我们在到达一个台阶时需要支付完一笔费用后才能前行那么前者可以转换为dp数组 —— 到达 i 位置的最小花费来表示后者的话则可以转换为cost数组 —— 从每个台阶上爬需要支付的费用 虽然是分成了两个子问题来进行求解但是呢题目给我们的要求是最小花费所以我们应该要取的是二者之中的较小值。那么【状态转移方程】即为
dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);那么当这个【状态转移方程】写出来后我们就要去考虑这个 初始化 的问题了因为上 0号 和 1号 台阶的时候我们是不需要支付任何费用的并且为了防止不越界我们在初始化的时候应该令dp[0] dp[1] 0 接下来的话就要去考虑我们的填表顺序了因为dp[i]是依赖于dp[i - 1]和dp[i - 2]所以我们需要先算出前面的2个数才能去得到这个dp[i]因此这个填表的顺序应该是 从左向右 最后的话就是我们的返回值dp[n]了 以下就是代码了
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();if(n 1) return n;// 1.定义dp数组vectorint dp(n 1);// 2.初始化dp[0] dp[1] 0;// 3.填充dp数组for(int i 2; i n; i){dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}// 4.返回结果return dp[n];}
};以下是提交后的结果 解法二 看完解法一之后我们再来看看解法二 首先的话还是一样我们要去确定这个 状态表示在解法二中dp[i]表示的 从i位置出发到达楼顶时的最小花费那么接下去就慢慢地推导这个【状态转移方程】再来回顾一下解法一dp[i]表示为到达i位置时的最小花费 那此时我们从i位置出发也可以分为两种 支付当前台阶所需费用并向后走一步从i 1位置到终点支付当前台阶所需费用并向后走二步从i 2位置到终点 将上面的两个分析式转换为公式的话为 cost[i] dp[i 1]cost[i] dp[i 2] 那么最后的这个【状态转移方程】即为
dp[i] min(cost[i] dp[i 1], cost[i] dp[i 2]);接下去我们需要考虑的就是这个初始化的问题首先读者要清楚的是我们在开这个dp数组的时候大小应该是多大呢是n呢还是n 1呢 立即揭晓答案应该是[n]为什么原因就在于我们到达n级台阶的时候是不需要支付任何费用的即dp[n] 0所以去开出这个空间也是浪费的所以这一块地方应该是作为 楼梯顶部 才对那么从dp[n - 1]到这个顶部的位置所需要支付的费用即为cost[n - 1]那么从这个dp[n - 2]到这个顶部的位置所需要支付的费用即为cost[n - 2] 接下去我们所需要考虑的就是 填表顺序通过【状态转移方程】很明显可以看出我们需要先获取到dp[i 1]、dp[i 2]的值才可以去推导出dp[i]的值所以我们的填表顺序应该是从右往左的才对 那最后需要考虑的就是返回值了在本解法中我们的dp数组表示的是 从第i个位置出发到达楼顶的最小花费因为我们可以选择从第[0]或第[1]个位置出发所有最后的结果就是取这两个位置所需花费的最小值 以下是代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();// 1.定义dp数组vectorint dp(n);// 2.初始化【防止越界】dp[n - 1] cost[n - 1], dp[n - 2] cost[n - 2];// 从后往前遍历for(int i n - 3; i 0; --i){dp[i] min(dp[i 1] cost[i], dp[i 2] cost[i]);}return min(dp[0], dp[1]);}
};来看看优化后的效率 0x05 解码方法*
力扣91. 解码方法
最后再来一道压轴题本题是力扣里中等难度的题目。AC本题可以让你对dp的理解进一步提升首先的话我们来分析一下题目所表示的含义在题目中会给到一个只包含数字的非空字符串s然后要我们去对这个字符串做解码的操作规则如下 A - 1B - 2C - 3Z - 26 根据上面的解码规则我们进一步来看题目要求因为这个字符串中所包含的不仅仅只有一个数字所以在解码的时候便需要涉及到多种的可能性最后所需要我们返回的也是解码方法的总数 了解了题目的基本规则后我们通过分析示例来进一步理解题目 首先看到示例1s “12”那我们的解码方式就有 两种一种是“A B”12一种则是L12然后看到示例2s “226”那我们的解码方式就有 三种一种是“B B F”226第二种是V F22,6第三种呢则是B Z226然后看到示例3s “06”对于这个而言其实是存在问题的因为“06”是无法映射到【F】的只有“6”才可以映射到【F】所以对于这种并不存在解码的方式 好当我们分析完题目中所给到的示例后就需要通过dp动态规划来解决本题接下去就是算法原理的讲解 首先第一步还一样定义出一个dp数组然后将其状态表示出来这里的dp[i]则表示 以 i 位置为结尾时的解码方法总数 然后接下去我们就要根据这个状态来推导出状态转移方程。我们通过这个dp数组来进行观察分析此处我们考虑到两种情况一个是就对i这个位置去做一个解码第二种呢则是i - 1和i这两个位置去结合结合完之后再去做解码的操作 那这个时候有同学就会有疑问了为什么不考虑i 1这个位置呢这个的话你就要反上去继续看我们所讲到的这个状态表示了。因为我们考虑的是 以 i 位置为结尾时的解码种数对于后面的情况此时还没有考虑到所以呢我们不需要去理会i 1这个位置 此时我们在求解dp数组的时候就就分为以下两种情况下 s[i]去单独解码分为两种情况那对于单独的一个数其取值就有1 ~ 9的可能性如果这个数为0的话则表示解码失败s[i - 1]与s[i]合并去解码的话我们就需要去考虑两个数了第一个数要比10来得大否则的话就要出现我们上面所讲到的06这种情况第二个数的话要比26来的小若二者都满足这种情况的话则可以解码成功否则的话就表示解码失败 那我们对i这个位置单独去做解码的话其实就相当于把[0, i - 1]解码的所有的方案数后面统一加一个字符就可以了具体如下图所示那我们要去找以i - 1为结尾的解码总数就可以表示为dp[i - 1] 接下去我们再来考虑第二种情况即我们要考虑到的是两位数合并后的情况那所需要求解的便是[0, i - 2]这段区间中的解码总数即dp[i - 2] 以下即为我们分析所得出的【状态转移方程】 接下去我们就来考虑初始化的问题 首先要初始化的位置相信读者在看了这么多道题之后应该很快就能反应过来了我们在初始化的时候应该去初始化dp[0]和dp[1]这两个位置的值对于dp[0]来说我们是对单个位置上的数去做一个解码那出现的情况也就只有【0】和【1】两种数据的范围要在0 ~ 9之间那对于dp[1]来说我们要对合并的两数去做一个解码那此时就会存在3种情况 [0]即为这二者都不存在的时候[1]即为这二者中只有一者存在的情况[2]即为二者都存在的情况 接下去我们再来看填表顺序 这一块很好理解通过我们的【状态转移方程】可以看出后面的数依赖于前面的数那么遍历的顺序即为从左往右
dp[i] dp[i - 1] dp[i - 2]最后的话是关于返回值这一块因为我们要找的是到第 i 个位置的解码总数不过题目给出的是一个字符串对于字符串的最后一个位置是n - 1那么我们最后返回的结果dp[i - 1] 由于本题代码比较得复杂所以接下去分步骤讲解一下
首先我们要做的就是创建出dp表
// 创建dp表
int n s.size();
vectorint dp(n);接下来要做的就是初始化工作首先要去做的是初始化dp[0]还记得我们上面分析的吗当这个编码的范围在1 ~ 9之间的时候所以在这里我们可以采取一个逻辑判断让dp[0]只接收当前s[0]这个字符的值不为0的情况
// 初始化dp[0]
dp[0] (s[0] ! 0);接下去呢我们考虑初始化dp[1]首先考虑到两数单独编码的情况若均不为0的话则表示可以进行解码
// 1.两数单独编码
if(s[0] ! 0 s[1] ! 0)dp[1] 1;接下去的话我们还需考虑两数结合的情况因为这边给到的是字符串所以我们在取的时候需要将其- ‘0’转换为数字才可以接下去根据我们刚才所分析的去判断这个数是否在符合的范围内若是的话才表示可以解码
// 2.两数结合
int t (s[0] - 0) * 10 s[1] - 0; // 字符串转数字
if(t 10 t 26) dp[1] 1;其后我们才去考虑这个【填表】的事情因为前两个位置dp[0]和dp[1]已经做了初始化所以我们从第3个位置开始即可然后你就可以发现这个填表的情况和我们在初始化时的场景非常类似这里就不细说了
// 填表
for(int i 2;i n; i) // 从第三个位置开始遍历
{// 单独编码的情况if(s[i] ! 0) dp[i] dp[i - 1]; // 两数结合的情况int t (s[i - 1] - 0) * 10 s[i] - 0;if(t 10 t 26) dp[i] dp[i - 2];
}最后的话返回dp[n - 1]即可
return dp[n - 1];以下是整体的代码展示
class Solution {
public:
// 状态转移公式
// dp[i] dp[i - 1] dp[i - 2]int numDecodings(string s) {// 创建dp表int n s.size();vectorint dp(n);// 初始化dp[0]dp[0] (s[0] ! 0);// 处理边界情况if(n 1) return dp[0];// 初始化dp[1]// 1.两数单独编码if(s[0] ! 0 s[1] ! 0)dp[1] 1;// 2.两数结合int t (s[0] - 0) * 10 s[1] - 0; // 字符串转数字if(t 10 t 26) dp[1] 1;// 填表for(int i 2;i n; i) // 从第三个位置开始遍历{// 单独编码的情况if(s[i] ! 0) dp[i] dp[i - 1]; // 两数结合的情况int t (s[i - 1] - 0) * 10 s[i] - 0;if(t 10 t 26) dp[i] dp[i - 2];}return dp[n - 1];}
};以下是执行结果 四、总结与提炼 最后来总结一下本文所学习的内容 在本文中我们学习到了大厂面试中非常喜欢考察一种算法类型叫做【动态规划】它也是令许多同学望而却步的绊脚石之一希望在阅读本文只后可以让你对dp动态规划有了一个清晰的认识首先我们对动态规划的基础理论有了一些认识清楚了什么是 动态规划 以及 动态规划的五部曲之后呢我们就展开对习题的讲解和分析从最基础的【斐波那契数】开始一直到较为复杂的【解码问题】随着一步步地深入不知读者是否对动态规划有了进一步的认识 以上就是本文所要介绍的所有内容感谢您的阅读
