跳到主要内容 剑指 Offer 动态规划与记忆化搜索解题总结 | 极客日志
C++ 算法
剑指 Offer 动态规划与记忆化搜索解题总结 基于剑指 Offer 第二版,整理了动态规划与记忆化搜索的十道经典例题。内容涵盖斐波那契数列、青蛙跳台阶、矩阵覆盖、正则表达式匹配、连续子数组最大和、数字翻译字符串、礼物最大价值及构建乘积数组等问题。通过递推、记忆化搜索及动态规划三种方式对比分析,提供 C++ 代码实现及核心逻辑推导,帮助读者掌握相关算法模型。
雪落无声 发布于 2026/3/30 更新于 2026/4/13 1 浏览前三题是同一种模型,所以我分别用递推、记忆化、动归来做。
一、JZ10 斐波那契数列
class Solution {
public :
int Fibonacci (int n) {
if (n==1 ||n==2 ) return 1 ;
int a=1 ,b=1 ,c=1 ;
while (n>2 ){
c=a+b;
a=b;
b=c;
--n;
}
return c;
}
};
二、扩展 JZ10 青蛙跳台阶
class Solution {
public :
int memory[41 ]={0 };
int jumpFloor (int n) {
if (n<=2 ) return n;
if (memory[n]) return memory[n];
memory[n]= (n )+ (n );
}
};
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown 转 HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
return
jumpFloor
-1
jumpFloor
-2
三、扩展 JZ10 矩阵覆盖 class Solution {
public :
int rectCover (int n) {
if (n<=2 ) return n;
vector<int > dp (n+1 ) ;
dp[1 ]=1 ,dp[2 ]=2 ;
for (int i=3 ;i<=n;++i) dp[i]=dp[i-1 ]+dp[i-2 ];
return dp[n];
}
};
四、扩展 JZ10 青蛙跳台阶扩展问题
动态规划 // f[n]=f[n-1]+f[n-2]……f[0]
// f[n-1]=f[n-2]+f[n-3]……f[0]
// 根据归纳法得 f[n]=2*f[n-1]
class Solution {
public :
int jumpFloorII (int number) {
vector<int > dp (number) ;
dp[0 ]=1 ;
for (int i=1 ;i<number;++i) dp[i]=dp[i-1 ]*2 ;
return dp[number-1 ];
}
};
递归 class Solution {
public :
int jumpFloorII (int number) {
if (number == 1 )return 1 ;
return 2 * jumpFloorII (number - 1 );
}
};
数学规律 根据规律 f[n]=2^(n-1),直接用 pow 函数
class Solution {
public :
int jumpFloorII (int number) {
if (number == 1 )return 1 ;
return pow (2 ,number-1 );
}
};
五、JZ19 正则表达式匹配 当 p[j]=='. '或者 p[j]==s[i] 那么 dp[i][j]=dp[i-1][j-1]
当 p[j]=='*'的时候,如果 p[j-1]=='. '那么 dp[i][j-2]||dp[i-1][j-2]……
如果 p[j-1]==s[i] 那么 dp[i][j-2]||dp[i-1][j-2]||……
我们可以当不匹配就是 dp[i][j-2],或者是 匹配一个然后保留 dp[i-1][j]
class Solution {
public :
bool match (string s, string p) {
int m=s.size (), n= p.size ();
vector<vector<bool >> dp (m+1 ,vector <bool >(n+1 ));
string sp = " " + p;
dp[0 ][0 ]=true ;
for (int j=2 ;j<=n;j+=2 )
if (sp[j]=='*' )dp[0 ][j]=true ;
else break ;
for (int i=1 ;i<=m;++i)
for (int j=1 ;j<=n;++j)
if (sp[j]=='*' )
dp[i][j]=dp[i][j-2 ]||(sp[j-1 ]==s[i]||sp[j-1 ]=='.' )&&dp[i-1 ][j];
else
dp[i][j]=(s[i]==sp[j]||sp[j]=='.' )&&dp[i-1 ][j-1 ];
return dp[m][n];
}
};
六、JZ42 连续子数组的最大和 dp[i] 表示以 i 位置为结尾时的最大子数组和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
int n;
cin>>n;
vector<int > nums (n) ,dp (n) ;
for (int i=0 ;i<n;++i) cin>>nums[i];
dp[0 ]=nums[0 ];
for (int i=1 ;i<n;++i) dp[i]=max (dp[i-1 ]+nums[i],nums[i]);
cout<<*max_element (dp.begin (),dp.end ())<<endl;
}
七、扩展 JZ42 连续子数组的最大和(二) 与上一题的区别在于我们不仅要统计最大的子数组和,还需要尽量选择最长的,而且还要把他们全都插入到数组里返回(需要记录区间)
class Solution {
public :
vector<int > FindGreatestSumOfSubArray (vector<int >& nums) {
int n=nums.size ();
vector<int > dp (n) ;
dp[0 ]=nums[0 ];
int begin=0 ;
int left=0 ,right=0 ;
int maxsum=nums[0 ];
for (int i=1 ;i<n;++i){
dp[i]=max (nums[i],dp[i-1 ]+nums[i]);
if (nums[i]+dp[i-1 ]<nums[i]) begin=i;
if (dp[i]>maxsum||dp[i]==maxsum&&(right-left+1 )<(i-begin+1 )){
maxsum=dp[i];
left=begin;
right=i;
}
}
vector<int > ret;
ret.reserve (right-left+1 );
for (int i=left;i<=right;++i) ret.emplace_back (nums[i]);
return ret;
}
};
八、JZ46 把数字翻译成字符串 // 有 s[i] 单独编码的时候 dp[i]+=dp[i-1]
// 当 s[i] 和 s[i-1] 一起编码的时候 dp[i]+=dp[i-2]
class Solution {
public :
int solve (string nums) {
if (nums=="0" ) return 0 ;
int n=nums.size ();
string sn = " " + nums;
vector<int > dp (n+1 ) ;
dp[0 ]=1 ;
dp[1 ]=(sn[1 ]!='0' );
for (int i=2 ;i<=n;++i){
if (sn[i]!='0' ) dp[i]+=dp[i-1 ];
int val=(sn[i-1 ]-'0' )*10 +sn[i]-'0' ;
if (10 <=val&&val<=26 ) dp[i]+=dp[i-2 ];
}
return dp[n];
}
};
九、JZ47 礼物的最大价值
动态规划 class Solution {
public :
int maxValue (vector<vector<int > >& nums) {
int m=nums.size (),n=nums[0 ].size ();
vector<vector<int >> dp (m+1 ,vector <int >(n+1 ));
for (int i=1 ;i<=m;++i)
for (int j=1 ;j<=n;++j)
dp[i][j]=max (dp[i-1 ][j],dp[i][j-1 ])+nums[i-1 ][j-1 ];
return dp[m][n];
}
};
记忆化搜索 class Solution {
public :
int m,n;
int maxValue (vector<vector<int > >& nums) {
m=nums.size (),n=nums[0 ].size ();
vector<vector<int >> memory (m,vector <int >(n));
return dfs (nums,m-1 ,n-1 ,memory);
}
int dfs (vector<vector<int > >& nums,int i,int j,vector<vector<int > >& memory) {
if (i==0 &&j==0 ) return nums[0 ][0 ];
if (memory[i][j]) return memory[i][j];
if (i==0 ) return memory[0 ][j]=nums[0 ][j]+dfs (nums,0 ,j-1 ,memory);
if (j==0 ) return memory[i][0 ]=nums[i][0 ]+dfs (nums,i-1 ,0 ,memory);
return memory[i][j]=nums[i][j]+max (dfs (nums,i-1 ,j,memory),dfs (nums,i,j-1 ,memory));
}
};
十、JZ66 构建乘积数组 vector<int > multiply (vector<int >& nums) {
int n=nums.size ();
if (n==1 ) return {};
vector<int > ret (n) ;
vector<int > dpq (n,1 ) ;
vector<int > dph (n,1 ) ;
for (int i=1 ;i<n;++i) dpq[i]=dpq[i-1 ]*nums[i-1 ];
for (int i=n-2 ;i>=0 ;--i) dph[i]=dph[i+1 ]*nums[i+1 ];
for (int i=0 ;i<n;++i) ret[i]=dpq[i]*dph[i];
return ret;
}