前三題是同一種模型，所以我分別用遞推、記憶化、動歸來做

一、p74-JZ10 斐波那契數列

斐波那契數列_牛客題霸_牛客網

class Solution {
public:int Fibonacci(int n) {// write code hereif(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==3if(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<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];}
};

四、擴展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<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) {//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<bool>> dp(m+1,vector<bool>(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 <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;
}

七、擴展p218-JZ42 連續子數組的最大和（二）

連續子數組的最大和(二)_牛客題霸_牛客網

?與上一題的區別在于我們不僅要統計最大的子數組和，還需要盡量選擇最長的，而且還要把他們全都插入到數組里返回（需要記錄區間）?

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;}
};

八、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<int> 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<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));}
};

十、p312-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;}
};