剑指offer第2版：动态规划+记忆化搜索

前三题是同一种模型，所以我分别用递推、记忆化、动归来做

一、p74-JZ10 斐波那契数列

斐波那契数列_牛客题霸_牛客网

class Solution {public: int Fibonacci(int n) { // write code here 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; }};

二、扩展p77-JZ10青蛙跳台阶

跳台阶_牛客题霸_牛客网

class Solution {public: //这题就用记忆化搜索 int memory[41]={0}; int jumpFloor(int n) { if(n<=2) return n;//考虑了1和2的情况 //此时至少是n==3 if(memory[n]) return memory[n]; return memory[n]=jumpFloor(n-1)+jumpFloor(n-2); }};

三、扩展p79-JZ10矩阵覆盖

矩形覆盖_牛客题霸_牛客网

class Solution {public: int rectCover(int n) { if(n<=2) return n; vector 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]; }};

四、扩展p78-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) { //动归 f[n]表示跳到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] vector 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) { //1或0都是1种 if(number == 1)return 1; //f(n) = 2*f(n-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); }};

 五、p124-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) { //dp[i][j]表示p[0,j]的子串能否匹配s[0,i]的子串 int m=s.size(), n= p.size(); vector<vector> dp(m+1,vector(n+1)); s=\' \'+s,p=\' \'+p; //为了方便下标的对应 //分析边界 *可以和前一个组成空串 dp[0][0]=true; for(int j=2;j<=n;j+=2) if(p[j]==\'*\')dp[0][j]=true; else break; //当p[j]==s[i]||p[j]==\'.\' dp[i][j]=dp[i-1][j-1] //当p[j]==\'*\' 此时他可以匹配空，也可以匹配前1个、前两个相同的 //*如果啥也不匹配 dp[i][j-2] 或者是干掉一个然后保留dp[i-1][j] for (int i=1;i<=m;++i) for (int j=1;j<=n;++j) if (p[j]==\'*\') dp[i][j]=dp[i][j-2]||(p[j-1]==s[i]||p[j-1]==\'.\')&&dp[i-1][j]; else dp[i][j]=(s[i]==p[j]||p[j]==\'.\')&&dp[i-1][j-1]; return dp[m][n]; } };

六、p218-JZ42连续子数组的最大和

连续子数组最大和_牛客题霸_牛客网

dp[i]表示以i位置为结尾时的最大子数组和 

#include #include #include using namespace std;int main() { int n; cin>>n; vector nums(n),dp(n); for(int i=0;i>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;}

七、扩展p218-JZ42 连续子数组的最大和（二）

连续子数组的最大和(二)_牛客题霸_牛客网

 与上一题的区别在于我们不仅要统计最大的子数组和，还需要尽量选择最长的，而且还要把他们全都插入到数组里返回（需要记录区间） 

class Solution {public: vector FindGreatestSumOfSubArray(vector& nums) { //连续子数组的最大和 dp[i]表示以i位置为结尾的最大和子数组 int n=nums.size(); vector 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]maxsum||dp[i]==maxsum&&(right-left+1)<(i-begin+1)){ maxsum=dp[i]; left=begin; right=i; } } vector ret; ret.reserve(right-left+1); for(int i=left;i<=right;++i) ret.emplace_back(nums[i]); return ret; }};

八、p231-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) { //dp[i]表示以i位置为结尾时一共有多少种编码的可能性 //有s[i]单独编码的时候 dp[i]+=dp[i-1] //当s[i]和s[i-1]一起编码的时候 dp[i]+=dp[i-2] if(nums==\"0\") return 0; int n=nums.size(); nums=\' \'+nums; vector dp(n+1); dp[0]=1;//其实没有意义，是为了确保填表的正确 dp[1]=(nums[1]!=\'0\'); for(int i=2;i<=n;++i){ if(nums[i]!=\'0\') dp[i]+=dp[i-1]; int val=(nums[i-1]-\'0\')*10+nums[i]-\'0\'; if(10<=val&&val<=26) dp[i]+=dp[i-2]; } return dp[n]; }};

九、p233-JZ47 礼物的最大价值

礼物的最大价值_牛客题霸_牛客网

动态规划 

class Solution {public: int maxValue(vector<vector >& nums) { int m=nums.size(),n=nums[0].size(); //dp[i][j]表示从i j位置选了之后的最大价值 vector<vector> dp(m+1,vector(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 >& nums) { m=nums.size(),n=nums[0].size(); //dp[i][j]表示从i j位置选了之后的最大价值 vector<vector> memory(m,vector(n)); return dfs(nums,m-1,n-1,memory);//统计最大价值 } int dfs(vector<vector >& nums,int i,int j,vector<vector >& 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)); }};

十、p312-JZ66 构建乘积数组

 构建乘积数组_牛客题霸_牛客网

使用前缀积和后缀积数组  然后构建结果集 

 vector multiply(vector& nums) { //前缀积和后缀积问题 int n=nums.size(); if(n==1) return {}; vector ret(n); vector dpq(n,1); vector dph(n,1); //前缀积 for(int i=1;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; }};