🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》 《数据结构与算法》 《C++知识内容》 《Linux系统知识》 《算法刷题指南》 《测评文章活动推广》 《大模型语言路线学习》
✨逆境不吐心中苦,顺境不忘来时路!✨
🎬 博主简介:
在算法学习的过程中,动态规划始终是一个绕不开的重要主题.它不仅是解决复杂问题的高效工具,也是面试和竞赛中出现频率极高的核心考点.对于初学者而言,动态规划之所以难,往往不在于代码实现本身,而在于如何理解"状态""转移"和"最优子结构"这些抽象概念.而斐波那契数列,正是理解动态规划思想最经典、最基础的入门模型.表面上看,斐波那契数列只是一个简单的递推问题:后一个数等于前两个数之和.但如果从算法设计的角度深入分析,就会发现其中蕴含着动态规划的核心思想——将原问题拆解为规模更小的子问题,并通过保存中间结果来避免重复计算,从而显著提升效率.也正因为如此,斐波那契数列常被视为学习动态规划的第一把钥匙.本文将围绕斐波那契数列模型展开,从暴力递归入手,逐步分析其时间复杂度问题,再引出记忆化搜索和自底向上的动态规划写法,帮助读者循序渐进地理解动态规划的本质与实现方式,为后续学习更复杂的动态规划问题打下坚实基础.废话不多说,下面跟着小编的节奏🎵一起去疯狂的学习吧!
目录
- 1.动态规划算法思想背景
- 2.斐波那契数列模型背景介绍
- 3.第N个泰波那契数(OJ题)
- 4.三步问题(OJ题)
- 5.使用最小花费爬楼梯(OJ题)
- 6.解码方法(OJ题)
1.动态规划算法思想背景
动态规划(Dynamic Programming,简称 DP)是一种通过分阶段求解问题、保存中间结果来提高计算效率的算法设计思想.它的核心理念在于:对于一个复杂问题,如果其求解过程可以拆分为若干个相互关联的子问题,那么就可以先求解子问题,再由子问题的结果逐步推出原问题的答案,从而避免大量重复计算.
动态规划思想最早由美国数学家理查德·贝尔曼(Richard Bellman)在 20 世纪 50 年代提出,最初主要应用于运筹学、最优化理论以及决策过程研究中.随着计算机科学的发展,这一思想逐渐被广泛应用到算法设计领域,成为解决最优化问题、计数问题、路径问题和序列问题的重要方法之一.
从本质上讲,动态规划是对暴力递归的一种优化.许多问题在递归求解时,往往会重复计算相同的子问题,导致时间复杂度急剧上升.而动态规划正是通过记录已经求出的状态结果,在后续计算中直接复用这些结果,进而将原本低效的指数级算法优化为多项式级别的高效算法.
动态规划能够成立,通常依赖两个关键条件:
- 问题具有最优子结构,即原问题的最优解可以由子问题的最优解构成;
- 问题具有重复子问题,即在求解过程中,相同的子问题会被多次访问.只有同时具备这些特征,才能通过状态定义和状态转移方程,将问题系统化地拆解并高效求解.
在实际学习中,动态规划不仅是一种算法技巧,更是一种分析问题和构建解法的思维方式.它要求我们从整体问题中抽象出"状态",找出状态之间的递推关系,并根据计算顺序设计合理的求解过程.因此,掌握动态规划,不仅有助于解决具体算法题,也能够提升对复杂问题结构的理解能力.
正因为动态规划兼具理论价值与实践意义,它已成为算法学习中的核心内容之一.无论是经典的斐波那契数列、背包问题，还是路径规划、最长公共子序列、区间合并等问题,背后都体现了动态规划"以空间换时间""由小推大"的基本思想.
2.斐波那契数列模型背景介绍
斐波那契数列是数学与计算机科学中一个非常经典的数列模型,通常定义为:前两个数固定为0和1,从第三项开始,每一项都等于前两项之和.即:
F ( 0 ) = 0 , F ( 1 ) = 1 F(0)=0,\quad F(1)=1 F(0)=0,F(1)=1
F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n ≥ 2 ) F(n)=F(n-1)+F(n-2)\quad (n\ge 2) F(n)=F(n−1)+F(n−2)(n≥2)
这一数列最早来源于中世纪数学家斐波那契提出的兔子繁殖问题.该问题通过描述兔群数量随时间增长的规律,引出了这样一种递推关系:当前阶段的结果,依赖于前面两个阶段的状态.这种"当前问题由更小规模子问题推导而来"的特点,使斐波那契数列成为研究递归思想和动态规划算法的典型案例.
在算法学习中,斐波那契数列之所以重要,并不仅仅因为它形式简单,而是因为它完整体现了动态规划问题的基本特征.首先,它具有明显的重复子问题,例如在递归求解 F ( n ) F(n)F(n)时, F ( n − 1 ) F(n-1)F(n−1)和 F ( n − 2 ) F(n-2)F(n−2)的计算过程中会反复出现相同的子问题;其次,它满足最优子结构或递推结构,即原问题的解可以由子问题的解直接构成.正因如此,斐波那契数列常被用作讲解暴力递归、记忆化搜索、状态转移方程以及空间优化等内容的入门模型.
从教学角度来看,斐波那契数列模型是连接"数学递推思想"和"程序设计实现"之间的重要桥梁.通过这个模型,学习者不仅可以直观理解递归到动态规划的优化过程,还能够逐步掌握如何抽象状态、设计转移方程以及分析算法复杂度.因此,斐波那契数列不仅是动态规划的起点,也为后续学习背包问题、路径问题、区间动态规划等更复杂的模型奠定了基础.
3.第N个泰波那契数(OJ题)
算法流程解法(动态规划)
- 状态表示:
这道题可以根据题目的要求直接定义出状态表示:
dp[i]表示：第i个泰波那契数的值. - 状态转移方程：
题目已经非常贴心的告诉我们了：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] - 初始化：
从我们的递推公式可以看出,dp[i]在i = 0以及i = 1的时候是没有办法进行推导的,因为dp[-2]或dp[-1]不是一个有效的数据.
因此我们需要在填表之前,将0, 1, 2位置的值初始化.题目中已经告诉我们dp[0] = 0,dp[1] = dp[2] = 1. - 填表顺序:
毫无疑问是从左往右. - 返回值:
应该返回dp[n]的值.
核心代码
1//使用一维数组 2class Solution { 3public: 4 //函数功能：求解第n个泰波那契数 5 //参数n：目标泰波那契数的下标 6 //返回值：第n个泰波那契数的值 7 int tribonacci(int n) { 8 //边界条件1：n=0返回0，n=1返回1（题目给定的初始值） 9 if (n == 0 || n == 1) 10 return n; 11 12 //定义dp数组：dp[i] 表示第i个泰波那契数 13 //数组大小为n+1，保证能存储到下标为n的元素 14 vector<int> dp(n + 1); 15 16 //初始化dp数组：题目给定的前3个泰波那契数初始值 17 dp[0] = 0; //第0个泰波那契数 18 dp[1] = 1; //第1个泰波那契数 19 dp[2] = 1; //第2个泰波那契数 20 21 //核心循环：从左往右填充dp数组（从第3个开始递推） 22 //泰波那契数递推公式：T(n) = T(n-1) + T(n-2) + T(n-3) 23 for (int i = 3; i <= n; i++) 24 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 25 26 //返回最终结果：第n个泰波那契数 27 return dp[n]; 28 } 29}; 30 31//滚动数组优化 32class Solution { 33public: 34 //函数功能：计算第n个泰波那契数（滚动数组优化版，空间复杂度O(1)） 35 //泰波那契数列规则：T(0)=0, T(1)=1, T(2)=1, T(n)=T(n-1)+T(n-2)+T(n-3) 36 int tribonacci(int n) { 37 //边界条件1：n=0时，直接返回0 38 if(n == 0) return 0; 39 //边界条件2：n=1或n=2时，直接返回1 40 if(n == 1 || n == 2) return 1; 41 42 //滚动变量定义： 43 //a 保存 T(i-3) 的值 44 //b 保存 T(i-2) 的值 45 //c 保存 T(i-1) 的值 46 //d 保存当前计算的 T(i) 的值 47 int a = 0, b = 1, c = 1, d = 0; 48 49 //从第3项开始，循环递推计算到第n项 50 for(int i = 3; i <= n; i++) 51 { 52 //核心递推公式：当前项 = 前三项之和 53 d = a + b + c; 54 //滚动更新变量：为下一次循环做准备 55 a = b; //原T(i-2) 变成 新的T(i-3) 56 b = c; //原T(i-1) 变成 新的T(i-2) 57 c = d; //新计算的T(i) 变成 新的T(i-1) 58 } 59 60 //循环结束后，d即为第n个泰波那契数 61 return d; 62 } 63}; 64
完整测试代码
1#include <iostream> 2using namespace std; 3 4class Solution { 5public: 6 int tribonacci(int n) { 7 if(n == 0) return 0; 8 if(n == 1 || n == 2) return 1; 9 10 int a = 0, b = 1, c = 1, d = 0; 11 for(int i = 3; i <= n; i++) 12 { 13 d = a + b + c; 14 a = b; 15 b = c; 16 c = d; 17 } 18 return d; 19 } 20}; 21 22int main() { 23 Solution sol; //创建解法对象 24 25 //定义测试用例（泰波那契数列标准值） 26 int testCases[] = {0, 1, 2, 3, 4, 5, 6, 10}; 27 //标准结果：T0=0, T1=1, T2=1, T3=2, T4=4, T5=7, T6=13, T10=149 28 29 cout << "泰波那契数列测试结果：" << endl; 30 //遍历测试所有用例 31 for(int n : testCases) { 32 int res = sol.tribonacci(n); 33 cout << "n = " << n << " -> 结果：" << res << endl; 34 } 35 36 return 0; 37} 38
4.三步问题(OJ题)
算法思路:解法(动态规划)
- 状态表示
这道题可以根据经验 + 题目要求直接定义出状态表示:
dp[i]表示：到达i位置时,一共有多少种方法. - 状态转移方程
以i位置状态的最近的一步,来分情况讨论:
如果dp[i]表示小孩上第i阶楼梯的所有方式,那么它应该等于所有上一步的方式之和:
i. 上一步上一级台阶，dp[i] += dp[i - 1];
ii. 上一步上两级台阶，dp[i] += dp[i - 2];
iii. 上一步上三级台阶，dp[i] += dp[i - 3];
综上所述,dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3].
需要注意的是,这道题目说明,由于结果可能很大,需要对结果取模.
在计算的时候,三个值全部加起来再取模,即 (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD 是不可取的,同学们可以试验一下,n 取题目范围内最大值时,网站会报错 signed integer overflow.
对于这类需要取模的问题,我们每计算一次(两个数相加/乘等),都需要取一次模.否则,万一发生了溢出,我们的答案就错了.
- 初始化
从我们的递推公式可以看出,dp[i]在i = 0，i = 1以及i = 2的时候是没有办法进行推导的,因为dp[-3]、dp[-2]或dp[-1]不是一个有效的数据.
因此我们需要在填表之前,将1, 2, 3位置的值初始化.
根据题意,dp[1] = 1,dp[2] = 2,dp[3] = 4. - 填表顺序
毫无疑问是从左往右. - 返回值
应该返回dp[n]的值.
核心代码
1class Solution { 2public: 3 //取模常量：防止数值溢出，题目要求结果对 1e9+7 取模 4 const int MOD = 1e9 + 7; 5 6 //函数功能：计算上 n 级台阶的总方法数 7 //规则：每次可以走 1 步、2 步 或 3 步 8 int waysToStep(int n) { 9 //动态规划标准解题四步走 10 //1. 创建 dp 表 11 //2. 初始化 12 //3. 填表 13 //4. 返回结果 14 15 //边界条件：n 为 1/2/3 时，直接返回固定结果（提前处理，避免数组操作） 16 if(n == 1 || n == 2) return n; 17 if(n == 3) return 4; 18 19 //1.创建 dp 表 20 //dp[i] 表示：上到第 i 级台阶，总共有多少种方法 21 //数组大小 n+1，保证下标能取到 n 22 vector<int> dp(n + 1); 23 24 //2.初始化 dp 数组（基础值，无法通过递推公式得到） 25 dp[1] = 1; //上1级台阶：只有1种方法（走1步） 26 dp[2] = 2; //上2级台阶：2种方法（1+1 / 2） 27 dp[3] = 4; //上3级台阶：4种方法（1+1+1 / 1+2 / 2+1 / 3） 28 29 //3.填表：从第4级开始，从左往右递推计算 30 //状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 31 //每一步相加后都取模，避免整数溢出（核心优化） 32 for(int i = 4; i <= n; i++) 33 dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD; 34 35 //4.返回结果：第n级台阶的总方法数 36 return dp[n]; 37 } 38}; 39
完整测试代码
1#include <iostream> 2#include <vector> 3using namespace std; 4 5class Solution { 6public: 7 const int MOD = 1e9 + 7; 8 9 int waysToStep(int n) { 10 //1. 创建 dp 表 11 //2. 初始化 12 //3. 填表 13 //4. 返回 14 15 //处理边界情况 16 if(n == 1 || n == 2) return n; 17 if(n == 3) return 4; 18 19 vector<int> dp(n + 1); 20 dp[1] = 1, dp[2] = 2, dp[3] = 4; 21 for(int i = 4; i <= n; i++) 22 dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD; 23 return dp[n]; 24 } 25}; 26 27int main() { 28 Solution sol; 29 //测试用例：台阶数 1~6 30 int testCases[] = {1, 2, 3, 4, 5, 6}; 31 32 cout << "三步上楼梯 测试结果：" << endl; 33 cout << "每次可走1/2/3级台阶，求上n级台阶的方法数" << endl; 34 cout << "----------------------------------------" << endl; 35 36 //遍历测试所有用例 37 for(int n : testCases) { 38 int res = sol.waysToStep(n); 39 cout << "台阶数 n = " << n << " → 总方法数：" << res << endl; 40 } 41 42 return 0; 43} 44
5.使用最小花费爬楼梯(OJ题)
算法思路:解法(动态规划)解法⼀：
- 状态表示：
这道题可以根据经验 + 题目要求直接定义出状态表示:
第一种：以i位置为结尾,
dp[i]表示：到达i位置时的最小花费.(注意:到达i位置的时候,i位置的钱不需要算上) - 状态转移方程：
根据最近的一步,分情况讨论:
- 先到达
i - 1的位置,然后支付cost[i - 1],接下来走一步走到i位置:
dp[i - 1] + cost[i - 1]; - 先到达
i - 2的位置,然后支付cost[i - 2],接下来走一步走到i位置:
dp[i - 2] + cost[i - 2].
- 初始化：
从我们的递推公式可以看出,我们需要先初始化i = 0,以及i = 1位置的值.容易得到dp[0] = dp[1] = 0,因为不需要任何花费,就可以直接站在第 0 层和第 1 层上. - 填表顺序：
根据状态转移方程可得,遍历的顺序是从左往右. - 返回值：
根据状态表示以及题目要求,需要返回dp[n]位置的值.
核心代码
1class Solution 2{ 3public: 4 //参数cost：每一级台阶对应的花费数组，每次可以爬1级或2级台阶 5 //目标：爬到楼梯顶部（最后一级台阶的上方）的最小花费 6 int minCostClimbingStairs(vector<int>& cost) 7 { 8 //获取台阶的总数量 9 int n = cost.size(); 10 11 //1.创建dp表 12 //dp[i] 表示：爬到第 i 级台阶位置的最小花费 13 //数组大小为 n+1：因为要爬到顶部（第n级位置），需要覆盖0~n所有位置 14 vector<int> dp(n + 1, 0); 15 16 //2.初始化dp数组 17 //初始状态：站在第0级、第1级台阶，不需要任何花费，直接站立 18 dp[0] = dp[1] = 0; 19 20 //3.填表：从第2级台阶开始，从左往右递推计算 21 for (int i = 2; i < n + 1; i++) 22 //状态转移方程： 23 //到达第i级台阶有两种方式： 24 //①从i-1级爬1步上来：总花费 = 到i-1级的最小花费 + i-1级台阶的花费 25 //②从i-2级爬2步上来：总花费 = 到i-2级的最小花费 + i-2级台阶的花费 26 //取两种方式的最小值，作为到达i级台阶的最小花费 27 dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]); 28 29 //4.返回结果 30 //dp[n] 就是爬到楼梯顶部的最小花费 31 return dp[n]; 32 } 33}; 34
完整测试代码
1#include <iostream> 2#include <vector> 3#include <algorithm> 4using namespace std; 5 6class Solution 7{ 8public: 9 int minCostClimbingStairs(vector<int>& cost) 10 { 11 int n = cost.size(); 12 //初始化一个 dp 表 13 vector<int> dp(n + 1, 0); 14 //初始化 15 dp[0] = dp[1] = 0; 16 //填表 17 for (int i = 2; i < n + 1; i++) 18 //根据状态转移方程得 19 dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]); 20 //返回结果 21 return dp[n]; 22 } 23}; 24 25int main() { 26 Solution sol; 27 28 //测试用例1：力扣官方示例1 29 vector<int> cost1 = {10, 15, 20}; 30 cout << "测试用例1：cost = [10,15,20]" << endl; 31 cout << "最小花费：" << sol.minCostClimbingStairs(cost1) << endl << endl; 32 33 //测试用例2：力扣官方示例2 34 vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; 35 cout << "测试用例2：cost = [1,100,1,1,1,100,1,1,100,1]" << endl; 36 cout << "最小花费：" << sol.minCostClimbingStairs(cost2) << endl; 37 38 return 0; 39} 40
算法思路:解法(动态规划)解法二：
- 状态表示：
这道题可以根据经验 + 题目要求直接定义出状态表示:
第二种：以i位置为起点.
dp[i]表示：从i位置出发,到达楼顶,此时的最小花费. - 状态转移方程：
根据最近的一步，分情况讨论:
- 支付
cost[i],往后走一步,接下来从i + 1的位置出发到终点：dp[i + 1] + cost[i]; - 支付
cost[i],往后走两步,接下来从i + 2的位置出发到终点：dp[i + 2] + cost[i];
我们要的是最小花费,因此 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i].
- 初始化：
为了保证填表的时候不越界,我们需要初始化最后两个位置的值,结合状态表示易得:
dp[n - 1] = cost[n - 1],dp[n - 2] = cost[n - 2] - 填表顺序：
根据状态转移方程可得,遍历的顺序是从右往左. - 返回值：
根据状态表示以及题目要求,需要返回dp[n]位置的值.
核心代码
1class Solution 2{ 3public: 4 // 函数功能：计算爬楼梯的最小花费（反向动态规划解法） 5 // 参数cost：每级台阶的花费数组，每次可爬1级或2级台阶 6 // 核心思路：从楼顶倒推，计算每个位置到楼顶的最小花费 7 int minCostClimbingStairs(vector<int>& cost) 8 { 9 //动态规划解题四步模板 10 //1.创建 dp 表 11 //2.初始化 12 //3.确定填表顺序 13 //4.确定返回值 14 15 //获取台阶的总数量 16 int n = cost.size(); 17 18 //1.创建 dp 表 19 //dp[i] 表示：从第 i 级台阶出发，到达楼顶的最小花费 20 vector<int> dp(n); 21 22 //2.初始化 dp 数组（最后两个台阶） 23 //最后一级台阶(n-1)：直接跳1步到楼顶，花费=当前台阶费用 24 dp[n - 1] = cost[n - 1]; 25 //倒数第二级台阶(n-2)：直接跳2步到楼顶，花费=当前台阶费用 26 dp[n - 2] = cost[n - 2]; 27 28 //3.填表顺序：从右往左（从 n-3 遍历到 0） 29 //状态转移方程：dp[i] = min(跳1步, 跳2步) + 当前台阶花费 30 for(int i = n - 3; i >= 0; i--) 31 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]; 32 33 //4.返回值 34 //可以选择从第0级 或 第1级台阶开始，取两者的最小值 35 return min(dp[0], dp[1]); 36 } 37}; 38
完整测试代码
1#include <iostream> 2#include <vector> 3#include <algorithm> 4using namespace std; 5 6class Solution 7{ 8public: 9 int minCostClimbingStairs(vector<int>& cost) 10 { 11 //1.创建 dp 表 12 //2.初始化 13 //3.填表顺序 14 //4.返回值 15 16 int n = cost.size(); 17 //dp[i] 表示：从第i级台阶出发，到达楼顶的最小花费 18 vector<int> dp(n); 19 //初始化最后两级台阶：直接跳到底楼顶，花费为当前台阶费用 20 dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]; 21 //从右往左填表，倒推计算每一级台阶的最小花费 22 for(int i = n - 3; i >= 0; i--) 23 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]; 24 // 可以从0级或1级台阶起步，取最小花费 25 return min(dp[0], dp[1]); 26 } 27}; 28 29int main() { 30 Solution sol; 31 32 // 测试用例1：力扣官方示例1 33 vector<int> cost1 = {10, 15, 20}; 34 cout << "测试用例1：cost = [10,15,20]" << endl; 35 cout << "最小花费：" << sol.minCostClimbingStairs(cost1) << endl << endl; 36 37 // 测试用例2：力扣官方示例2 38 vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; 39 cout << "测试用例2：cost = [1,100,1,1,1,100,1,1,100,1]" << endl; 40 cout << "最小花费：" << sol.minCostClimbingStairs(cost2) << endl; 41 42 return 0; 43} 44
6.解码方法(OJ题)
算法思路:解法(动态规划):
- 状态表示：
根据以往的经验,对于大多数线性dp,我们经验上都是以某个位置结束或者开始做文章,这里我们继续尝试用i位置为结尾结合题目要求来定义状态表示.
dp[i]表示：字符串中[0, i]区间上,一共有多少种编码方法. - 状态转移方程：
定义好状态表示,我们就可以分析i位置的dp值,如何由前面或者后面的信息推导出来.
关于i位置的编码状况,我们可以分为下面两种情况:
i. 让i位置上的数单独解码成一个字母;
ii. 让i位置上的数与i - 1位置上的数结合,解码成一个字母.
下面我们就上面的两种解码情况,继续分析:
- 让
i位置上的数单独解码成一个字母,就存在解码成功和解码失败两种情况:
i. 解码成功：当i位置上的数在[1, 9]之间的时候,说明i位置上的数是可以单独解码的,那么此时[0, i]区间上的解码方法应该等于[0, i - 1]区间上的解码方法.因为[0, i - 1]区间上的所有解码结果,后面填上一个i位置解码后的字母就可以了.此时dp[i] = dp[i - 1];
ii. 解码失败：当i位置上的数是0的时候,说明i位置上的数是不能单独解码的,那么此时[0, i]区间上不存在解码方法.因为i位置如果单独参与解码,但是解码失败了,那么前面做的努力就全部白费了.此时dp[i] = 0. - 让
i位置上的数与i - 1位置上的数结合在一起,解码成一个字母,也存在解码成功和解码失败两种情况:
i. 解码成功：当结合的数在[10, 26]之间的时候,说明[i - 1, i]两个位置是可以解码成功的,那么此时[0, i]区间上的解码方法应该等于[0, i - 2]区间上的解码方法,原因同上.此时dp[i] = dp[i - 2];
ii. 解码失败：当结合的数在[0, 9]和[27, 99]之间的时候,说明两个位置结合后解码失败(这里一定要注意00 01 02 03 04 ……这几种情况),那么此时[0, i]区间上的解码方法就不存在了,原因依旧同上.此时dp[i] = 0.
综上所述：dp[i] 最终的结果应该是上面四种情况下,解码成功的两种的累加和(因为我们关心的是解码方法,既然解码失败,就不用加入到最终结果中去),因此可以得到状态转移方程(dp[i] 默认初始化为 0):
i. 当 s[i] 上的数在 [1, 9] 区间上时：dp[i] += dp[i - 1]；
ii. 当 s[i - 1] 与 s[i] 上的数结合后,在 [10, 26] 之间的时候：dp[i] += dp[i - 2];
如果上述两个判断都不成立,说明没有解码方法,dp[i] 就是默认值 0.
- 初始化：
方法一(直接初始化):
由于可能要用到i - 1以及i - 2位置上的dp值,因此要先初始化前两个位置.
初始化 dp[0]：
i. 当 s[0] == '0' 时,没有编码方法,结果 dp[0] = 0;
ii. 当 s[0] != '0' 时,能编码成功,dp[0] = 1
初始化 dp[1]：
i. 当 s[1] 在 [1, 9] 之间时,能单独编码,此时 dp[1] += dp[0](原因同上,dp[1] 默认为 0 )
ii. 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时,说明在前两个字符中,又有一种编码方式,此时 dp[1] += 1
方法二(添加辅助位置初始化):
可以在最前面加上一个辅助结点,帮助我们初始化.使用这种技巧要注意两个点:
i. 辅助结点里面的值要保证后续填表是正确的;
ii. 下标的映射关系
- 填表顺序：
毫无疑问是从左往右 - 返回值：
应该返回dp[n - 1]的值,表示在[0, n - 1]区间上的编码方法.
核心代码
1//使⽤直接初始化的⽅式解决问题 2class Solution 3{ 4public: 5 //规则：1-26 分别对应 A-Z，0不能单独解码，0开头的数字无法解码 6 int numDecodings(string s) 7 { 8 int n = s.size(); //获取字符串长度 9 vector<int> dp(n); //1.创建dp表 10 //dp[i] 表示：字符串 s[0...i] 区间的解码方法总数 11 12 //2.初始化dp数组：处理第一个字符 13 // 第一个字符非0，有1种解码方法；为0，无法解码（0种） 14 dp[0] = s[0] != '0'; 15 //边界情况：字符串只有1个字符，直接返回结果 16 if(n == 1) return dp[0]; 17 18 //初始化第二个字符 dp[1] 19 //情况1：第二个字符单独解码（要求 1<=s[1]<=9），方法数 += 第一个字符的解码数 20 if(s[1] <= '9' && s[1] >= '1') 21 dp[1] += dp[0]; 22 //情况2：前两个字符组合解码（要求数值在 10~26 之间），方法数 +1 23 int t = (s[0] - '0') * 10 + s[1] - '0'; //字符转数字，计算组合值 24 if(t >= 10 && t <= 26) 25 dp[1] += 1; 26 27 //3. 填表：从第三个字符开始，从左往右递推 28 for(int i = 2; i < n; i++) 29 { 30 //情况1：当前字符单独解码（1-9有效），方法数 += 前一位的解码数 31 if(s[i] <= '9' && s[i] >= '1') 32 dp[i] += dp[i - 1]; 33 //情况2：当前字符与前一个字符组合解码（10-26有效） 34 int t = (s[i - 1] - '0') * 10 + s[i] - '0'; 35 if(t >= 10 && t <= 26) 36 dp[i] += dp[i - 2]; //方法数 += 前两位的解码数 37 } 38 39 //4. 返回结果：整个字符串的解码方法总数 40 return dp[n - 1]; 41 } 42}; 43 44 45//使⽤添加辅助结点的⽅式初始化 46class Solution 47{ 48public: 49 //优化点：使用 n+1 大小的dp数组 + 虚拟下标，简化初始化逻辑，避免边界判断 50 int numDecodings(string s) 51 { 52 int n = s.size(); //获取字符串的长度 53 //1.创建dp表：dp[i] 表示 字符串前 i 个字符的解码方法总数 54 vector<int> dp(n + 1); 55 56 //2.初始化dp数组 57 dp[0] = 1; //虚拟节点：前0个字符（空字符串）有1种解码方法，保证后续计算合法 58 dp[1] = s[0] != '0'; //前1个字符：非0则1种方法，为0则0种 59 60 //3.填表：从左往右遍历，i 代表前i个字符 61 for (int i = 2; i <= n; i++) 62 { 63 //情况1：第 i 个字符（s[i-1]）单独编码 64 //字符不为0时有效，解码方法数 += 前i-1个字符的方法数 65 if (s[i - 1] != '0') 66 dp[i] += dp[i - 1]; 67 68 //情况2：第 i-1 和 i 个字符（s[i-2]、s[i-1]）联合编码 69 int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0'; 70 //组合数字在 10~26 之间时有效，解码方法数 += 前i-2个字符的方法数 71 if (t >= 10 && t <= 26) 72 dp[i] += dp[i - 2]; 73 } 74 75 //4.返回结果：整个字符串（前n个字符）的解码方法总数 76 return dp[n]; 77 } 78}; 79
完整测试代码
1#include <iostream> 2#include <vector> 3#include <string> 4using namespace std; 5 6class Solution 7{ 8public: 9 int numDecodings(string s) 10 { 11 //优化版动态规划：使用虚拟节点简化初始化 12 int n = s.size(); 13 //dp[i] 表示：字符串前 i 个字符的解码方法总数 14 vector<int> dp(n + 1); 15 dp[0] = 1; //虚拟节点：空字符串的解码方法为1，保证后续计算合法 16 dp[1] = s[0] != '0'; //第一个字符非0则1种方法，为0则0种 17 18 //填表：从左往右递推计算 19 for (int i = 2; i <= n; i++) 20 { 21 //情况1：当前字符单独编码（非0有效） 22 if (s[i - 1] != '0') 23 dp[i] += dp[i - 1]; 24 //情况2：当前字符与前一字符联合编码（10~26有效） 25 int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0'; 26 if (t >= 10 && t <= 26) 27 dp[i] += dp[i - 2]; 28 } 29 //返回整个字符串的解码方法总数 30 return dp[n]; 31 } 32}; 33 34int main() { 35 Solution sol; 36 37 //测试用例1：力扣官方示例1 38 string s1 = "12"; 39 cout << "测试用例1：s = \"" << s1 << "\"" << endl; 40 cout << "解码方法数：" << sol.numDecodings(s1) << endl << endl; 41 42 //测试用例2：力扣官方示例2 43 string s2 = "226"; 44 cout << "测试用例2：s = \"" << s2 << "\"" << endl; 45 cout << "解码方法数：" << sol.numDecodings(s2) << endl << endl; 46 47 //测试用例3：包含无效0的情况 48 string s3 = "06"; 49 cout << "测试用例3：s = \"" << s3 << "\"" << endl; 50 cout << "解码方法数：" << sol.numDecodings(s3) << endl << endl; 51 52 //测试用例4：边界情况-单个字符0 53 string s4 = "0"; 54 cout << "测试用例4：s = \"" << s4 << "\"" << endl; 55 cout << "解码方法数：" << sol.numDecodings(s4) << endl << endl; 56 57 //测试用例5：边界情况-单个有效字符 58 string s5 = "1"; 59 cout << "测试用例5：s = \"" << s5 << "\"" << endl; 60 cout << "解码方法数：" << sol.numDecodings(s5) << endl; 61 62 return 0; 63} 64
🚀真正的勇者不是流泪的人,而是含泪奔跑的人!
敬请期待下一篇文章内容:【动态规划算法】（从入门到精通:路径问题）
每日心灵鸡汤:“我们吞咽了太多意义,其实生命只需要呼吸”
人们总是喜欢为各种事情赋予特定的意义,以显示其存在价值.于是,为着这三言两语的意义,我们久经风霜又翻山越岭,遍体鳞伤还要咬着牙说一句"坚持不懈,久炼成钢".像是往鸟儿的足上绑了块石头,谁飞得更高,谁就是最值得嘉奖的鸟儿.我们都忘了,其实一开始,它们只需要飞翔,而不需要比较飞翔之高低.
一如我们的生命,只需要呼吸就够了,不用驮着石头蹉跎.
《【动态规划算法】（斐波那契数列模型详解）》 是转载文章，点击查看原文。
