【2023/4/6-4/12】动态规划
学习链接：
动态规划解题套路框架
动态规划设计：最长递增子序列
动态规划设计：最大子数组
1.单词拆分
题目来源：139. 单词拆分
题解：
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n=s.size();vector<bool> dp(n+1);dp[0]=true;unordered_set<string> set;for(auto word:wordDict){set.insert(word);}for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(dp[j]&&set.find(s.substr(j,i-j))!=set.end()){dp[i]=true;break;}}}return dp[n];}
};
//考虑字典树法
2.跳跃游戏 VI
题目来源：1696. 跳跃游戏 VI
题解：
class Solution {
public:int maxResult(vector<int>& nums, int k) {int n=nums.size();priority_queue<pair<int,int>> q;vector<int> f(n,INT_MIN/2);f[0]=nums[0];q.emplace(nums[0],0);for(int i=1;i<n;i++){while(i-q.top().second>k)q.pop();f[i]=q.top().first+nums[i];q.emplace(f[i],i);}return f[n-1];}
};
3.不同的子序列【困难】
题目来源：115. 不同的子序列
题解：
class Solution {
public:int numDistinct(string s, string t) {int m=s.size(),n=t.size();if(m<n) return 0;vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=0;i<=m;i++)dp[i][n]=1;//for(int j=0;j<=n-1;j++)//dp[m][j]=0;for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){if(s[i]==t[j])dp[i][j]=dp[i+1][j+1]+dp[i+1][j];elsedp[i][j]=dp[i+1][j];}}return dp[0][0];}
};
4.出界的路径数【】
题目来源：576. 出界的路径数
题解：
class Solution {
public:int MOD=1e9+7;vector<vector<vector<long long>>> dp;vector<vector<int>> dir={{-1,0},{1,0},{0,-1},{0,1}};int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {int ans;dp.resize(m, vector<vector<long long>>(n, vector<long long>(maxMove + 1)));dp[startRow][startColumn][maxMove]=0ll;ans=dfs(m,n,maxMove,startRow,startColumn,maxMove);return ans;}long long dfs(int m,int n,int maxMove,int i,int j,int k){if(k < 0) return 0;if(i > k && m - i > k && j > k && n - j > k) return 0; /// 剪枝if(i < 0 || i >= m || j < 0 || j >= n) return 1; if(dp[i][j][k] != 0) return dp[i][j][k];for(int a = 0; a < 4; ++a){int x = i + dir[a][0];int y = j + dir[a][1];dp[i][j][k] = (dp[i][j][k] + dfs(m, n, maxMove, x, y, k - 1)) % MOD;}return dp[i][j][k];}
};
5.路径的数目
题目来源：剑指 Offer II 098. 路径的数目
题解：
//自解
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n));for(int j=0;j<n;j++)dp[0][j]=1;for(int i=0;i<m;i++)dp[i][0]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++)dp[i][j]=dp[i-1][j]+dp[i][j-1];}return dp[m-1][n-1];}
};
//评论区他解：压缩为一维
class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n+1);dp[1]=1;//到起点的路径数为1for(int i=0;i<m;++i) {for(int j=1;j<=n;++j) {dp[j]+=dp[j-1];}}return dp[n];}
};
6.粉刷房子
题目来源：剑指 Offer II 091. 粉刷房子
题解：
//一维
class Solution {
public:int minCost(vector<vector<int>>& costs) {int n=costs.size();vector<int> dp(3);for(int j=0;j<3;j++)dp[j]=costs[0][j];for(int i=1;i<n;i++){vector<int> curdp(3);curdp[0]=min(dp[1],dp[2])+costs[i][0];curdp[1]=min(dp[0],dp[2])+costs[i][1];curdp[2]=min(dp[0],dp[1])+costs[i][2];dp=curdp;}return *min_element(dp.begin(),dp.end());}
};//二维
class Solution {
public:int minCost(vector<vector<int>>& costs) {int n=costs.size();vector<vector<int>> dp(n,vector<int>(3));for(int j=0;j<3;j++)dp[0][j]=costs[0][j];for(int i=1;i<n;i++){dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0];dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i][1];dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i][2];}return min(min(dp[n-1][1],dp[n-1][2]),dp[n-1][0]);}
};
7.通配符匹配
题目来源：44. 通配符匹配
题解：
class Solution {
public:bool isMatch(string s, string p) {int m=s.size(),n=p.size();vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));dp[0][0]=true;for(int i=1;i<=n;i++){if(p[i-1]=='*')dp[0][i]=true;elsebreak;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p[j-1]=='*')dp[i][j]=dp[i][j-1]|dp[i-1][j];else if(p[j-1]=='?' ||s[i-1]==p[j-1])dp[i][j]=dp[i-1][j-1];}}return dp[m][n];}
};
8.正则表达式匹配
题目来源：10. 正则表达式匹配
c++在函数中定义函数
知识点：
lambda 表达式定义了一个匿名函数，并且可以捕获一定范围内的变量。lambda 表达式的语法形式可简单归纳如下：
1| [ capture ] ( params ) opt -> ret { body; };
其中：
- capture 是捕获列表，空表示不捕获任何变量；&表示捕获外部作用域中所有变量，并作为引用在函数体中使用（按引用捕获）；=表示捕获外部作用域中所有变量，并作为副本在函数体中使用（按值捕获）；=，&foo表示按值捕获外部作用域中所有变量，并按引用捕获 foo 变量。bar按值捕获 bar 变量，同时不捕获其他变量；this表示捕获当前类中的 this 指针，让 lambda 表达式拥有和当前类成员函数同样的访问权限。如果已经使用了 & 或者 =，就默认添加此选项。捕获 this 的目的是可以在 lamda 中使用当前类的成员函数和成员变量。
- params 是参数表，
- opt 是函数选项，
- ret 是返回值类型，
- body是函数体
题解：
class Solution {
public:string tmpp,tmps;bool match(int i,int j){if(i==0)return false;if(tmpp[j-1]=='.')return true;return tmps[i-1]==tmpp[j-1];}bool isMatch(string s, string p) {tmpp=p;tmps=s;int m=s.size(),n=p.size();vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));dp[0][0]=true;for(int i=0;i<=m;i++){for(int j=1;j<=n;j++){if(p[j-1]=='*'){dp[i][j]=dp[i][j]|dp[i][j-2];if(match(i,j-1))dp[i][j]=dp[i][j]|dp[i-1][j];}else{if(match(i,j))dp[i][j]=dp[i-1][j-1];elsedp[i][j]=false;}}}return dp[m][n];}
};//解法②
class Solution {
public:bool isMatch(string s, string p) {int lens=s.size();int lenp=p.size();vector<vector<bool>> dp(lens+1,vector<bool>(lenp+1,false));//因为包含了空字串的情况//初始化 dp[0][0]=true;//两个空字串for(int j=1;j<lenp+1;j++)//找出s为空 但p因为* 为空的情况{if(p[j]=='*'){dp[0][j+1]=dp[0][j-1];}}//更新for(int i=1;i<lens+1;i++){for(int j=1;j<lenp+1;j++){if(s[i-1]==p[j-1]||p[j-1]=='.')//情况1：符合，直接更新{dp[i][j]=dp[i-1][j-1];}else if(p[j-1]=='*')//情况2：考虑*的情况{if(s[i-1]==p[j-2]||p[j-2]=='.'){dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-1][j];//分别是 重复0次；重复一次；重复两次及以上！！！}else//s[i-1] p[j-2]不匹配 *需要重复0次{dp[i][j]=dp[i][j-2];}}}}return dp[lens][lenp];}
};
9.最长递增子序列
常规法：
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。int lengthOfLIS(vector<int>& nums) {// 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度vector<int> dp(nums.size(), 1);// base case：dp 数组全都初始化为 1for (int i = 0; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}}int res = 0;for (int i = 0; i < dp.size(); i++) {res = max(res, dp[i]);}return res;
}二分查找法：
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。// 最长递增子序列
int lengthOfLIS(vector<int>& nums) {int piles = 0; // 牌堆数初始化为 0vector<int> top(nums.size()); // 牌堆数组 topfor (int i = 0; i < nums.size(); i++) {int poker = nums[i]; // 要处理的扑克牌/* 搜索左侧边界的二分查找 */int left = 0, right = piles; // 搜索区间为 [left, right)while (left < right) {int mid = (left + right) / 2; // 防溢出if (top[mid] > poker) {right = mid;} else if (top[mid] < poker) {left = mid + 1;} else {right = mid;}}/*/// 没找到合适的牌堆，新建一堆if (left == piles) piles++;// 把这张牌放到牌堆顶top[left] = poker;}// 牌堆数就是 LIS 长度return piles;
}
