基于剑指 Offer 第二版，整理了动态规划与记忆化搜索的十道经典例题。内容涵盖斐波那契数列、青蛙跳台阶、矩阵覆盖、正则表达式匹配、连续子数组最大和、数字翻译字符串、礼物最大价值及构建乘积数组等问题。通过递推、记忆化搜索及动态规划三种方式对比分析，提供 C++ 代码实现及核心逻辑推导，帮助读者掌握相关算法模型。
前三题是同一种模型，所以我分别用递推、记忆化、动归来做。
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;
}
};
class Solution {
public:
int memory[41]={0};
int jumpFloor(int n) {
if(n<=2) return n; // 考虑了 1 和 2 的情况
if(memory[n]) return memory[n];
memory[n]=(n)+(n);
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
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];
}
};
// 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) {
// 动归：f[n] 表示跳到 n 台阶一共有几种跳法
vector<int> dp(number);
dp[0]=1;
for(int i=1;i<number;++i) dp[i]=dp[i-1]*2;
return dp[number-1];
}
};
f[n]=2*f[n-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);
}
};
当 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) {
// dp[i][j] 表示 p[0,j] 的子串能否匹配 s[0,i] 的子串
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];
}
};
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;
}
与上一题的区别在于我们不仅要统计最大的子数组和，还需要尽量选择最长的，而且还要把他们全都插入到数组里返回（需要记录区间）
class Solution {
public:
vector<int> FindGreatestSumOfSubArray(vector<int>& nums) {
// 连续子数组的最大和 dp[i] 表示以 i 位置为结尾的最大和子数组
int n=nums.size();
vector<int> dp(n);
dp[0]=nums[0];
int begin=0; // 标记起始位置和 i 做一段区间
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;
}
};
// 有 s[i] 单独编码的时候 dp[i]+=dp[i-1] // 当 s[i] 和 s[i-1] 一起编码的时候 dp[i]+=dp[i-2]
class Solution {
public:
int solve(string nums) {
// dp[i] 表示以 i 位置为结尾时一共有多少种编码的可能性
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];
}
};
class Solution {
public:
int maxValue(vector<vector<int> >& nums) {
int m=nums.size(),n=nums[0].size();
// dp[i][j] 表示从 i j 位置选了之后的最大价值
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();
// dp[i][j] 表示从 i j 位置选了之后的最大价值
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));
}
};
使用前缀积和后缀积数组，然后构建结果集
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;
}
