网站及app建设,安徽省交通运输厅,长沙营销推广,室内设计师找图片的网站这里写目录标题 139. 单词拆分322. 零钱兑换300. 最长递增子序列120. 三角形最小路径和64. 最小路径和63. 不同路径 II5. 最长回文子串#xff08;回文dp#xff09;⭐97. 交错字符串⭐#xff08;抽象成路径问题#xff09;221. 最大正方形⭐ 139. 单词拆分
class Soluti… 这里写目录标题 139. 单词拆分322. 零钱兑换300. 最长递增子序列120. 三角形最小路径和64. 最小路径和63. 不同路径 II5. 最长回文子串回文dp⭐97. 交错字符串⭐抽象成路径问题221. 最大正方形⭐ 139. 单词拆分
class Solution {
public:const int N305;bool wordBreak(string s, vectorstring wordDict) {vectorbool dp(N,false);setstring S;S.clear();for(int i0;iwordDict.size();i){S.insert(wordDict[i]);}dp[0]true;int ns.size();for(int i1;in;i){//从头开始长度为i的子串for(int j0;ji;j){if(dp[j]){string strs.substr(j,i-1-(j-1));//0123if(S.find(str)!S.end()){dp[i]true;}}}}return dp[n];}
};322. 零钱兑换
class Solution {
public:const int inf0x3f3f3f3f;int coinChange(vectorint coins, int amount) {vectorint dp(amount1,inf);// dp[i]表示凑出金额i最少需要的硬币个数dp[0]0;int ncoins.size();for(int i1;iamount;i){for(int j0;jn;j){if(icoins[j]){dp[i]min(dp[i],dp[i-coins[j]]1);}}}if(dp[amount]inf)return -1;else return dp[amount];}
};恰好装满型完全背包
class Solution {
public:const int inf0x3f3f3f3f;int coinChange(vectorint coins, int amount) {vectorint dp(amount1,inf);// dp[i]表示凑出金额i最少需要的硬币个数dp[0]0;int ncoins.size();for(int j0;jn;j){for(int icoins[j];iamount;i){if(icoins[j]){dp[i]min(dp[i],dp[i-coins[j]]1);}}}if(dp[amount]inf)return -1;else return dp[amount];}
};300. 最长递增子序列
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint dp(n5,1);// dp[0]0;int res1;for(int i0;in;i){//i是上升子序列最后一个元素的下标for(int j0;ji;j){if(nums[i]nums[j]){dp[i]max(dp[i],dp[j]1);resmax(res,dp[i]);}}}return res;}
};贪心思想碰到小的元素尽可能放在前面 最后得到的最长上升子序列假设存储在d数组中d数组的演变过程 来了个更大的元素大于d[len]), 直接插入在末尾 如果小找到大于nums[i] 的第一个元素替换掉
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint d(n5,1);int len0;d[len]nums[0];for(int i1;in;i){if(nums[i]d[len]){d[len]nums[i];}else{//找到第一个大于nums[i]的d[k] 换掉int l0,rlen;while(lr){int mid(lr)/2;// if(d[mid]nums[i])rmid;// else lmid1;找最大// if(d[mid]nums[i])rmid;// else lmid1;if(d[mid]nums[i])lmid1;else rmid;}d[l]nums[i];}}return len1;}
};lower_bound,找到大于等于nums[i]的第一个元素
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint d;for(int i0;in;i){
vectorint::iterator it lower_bound(d.begin() , d.end() ,nums[i]);
if(itd.end())d.push_back(nums[i]);
elseswap(*it,nums[i]);}return d.size();}
};120. 三角形最小路径和
倒三角形注意下标
class Solution {
public:int minimumTotal(vectorvectorint triangle) {int mtriangle.size();// int ntriangle[0].size();vectorvectorint dp(m,vectorint(m,0));dp[0][0]triangle[0][0];// int res0x3f3f3f3f;int res2e610;for(int i1;im;i){for(int j0;ji;j){if(j0)dp[i][j]dp[i-1][j]triangle[i][j];else if(ji)dp[i][j]dp[i-1][j-1]triangle[i][j];else dp[i][j]min(dp[i-1][j-1],dp[i-1][j])triangle[i][j];// if(im-1)resmin(res,dp[i][j]);怎么放在这儿就不行了why not}}// res*min_element(dp[m-1].begin(),dp[m-1].end());// resmin(2000010,-10);for(int i0;im;i)resmin(res,dp[m-1][i]);return res;}
};64. 最小路径和
class Solution {
public:int minPathSum(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();vectorvectorint dp(m,vectorint(n,0));dp[0][0]grid[0][0];for(int j1;jn;j)dp[0][j]dp[0][j-1]grid[0][j];for(int i1;im;i){for(int j0;jn;j){if(j0)dp[i][j]dp[i-1][j]grid[i][j];else dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j];}}return dp[m-1][n-1];}
};63. 不同路径 II
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int mobstacleGrid.size();int nobstacleGrid[0].size();vectorvectorint dp(m,vectorint(n,0));if(!obstacleGrid[0][0])dp[0][0]1;for(int i1;in;i)if(!obstacleGrid[0][i])dp[0][i]dp[0][i-1];for(int i1;im;i){for(int j0;jn;j){if(!obstacleGrid[i][j]){if(j0)dp[i][j]dp[i-1][j];else dp[i][j]dp[i-1][j]dp[i][j-1];}}}return dp[m-1][n-1];}
};5. 最长回文子串回文dp⭐
class Solution {
public:string longestPalindrome(string s) {int Ls.size();vectorvectorbool dp(L1,vectorbool(L1,false));int maxlen1;int pos0;for(int len1;lenL;len){for(int i0;ilen-1L;i){int jilen-1;// dp[i][j]这段是否为回文串if(len1)dp[i][j]true;else{if(s[i]s[j]){if(len2||len3){dp[i][j]true;}else {dp[i][j]dp[i1][j-1];}}}if(dp[i][j]){if(lenmaxlen){maxlenlen;posi;}} }}// return s.substr(pos,maxlen);string res;for(int len1;lenL;len){for(int i0;ilen-1L;i){int jilen-1;if(dp[i][j])ress.substr(i,len);}}return res;}
};class Solution {
public:string longestPalindrome(string s) {int Ls.size();vectorvectorbool dp(L1,vectorbool(L1,false));for(int i0;iL;i)dp[i][i]true;int pos0;int maxlen1;for(int len2;lenL;len){for(int i0;ilen-1L;i){int jilen-1;// dp[i][j]这段是否为回文串if(s[i]s[j]){if(len2||len3){dp[i][j]true;}else {dp[i][j]dp[i1][j-1];}}if(dp[i][j]){maxlenlen;posi;} }}return s.substr(pos,maxlen);// string res;// for(int len1;lenL;len){// for(int i0;iL;i){// int jilen-1;// if(dp[i][j])ress.substr(i,len);// }// }// return res;}
};97. 交错字符串⭐抽象成路径问题
s1s2交错组成s3把s1s2抽象为横纵坐标s3抽象为向右向下的路径
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int ms1.size();int ns2.size();if(mn!s3.size())return false;// , ,avector vectorbool dp(m1,vectorbool(n1,false));// 一些最基础的子问题的初始化处理dp[0][0]true;for(int len1;lenm;len){if(s1[len-1]s3[len-1])dp[len][0]true;else break;}for(int len1;lenn;len){if(s2[len-1]s3[len-1])dp[0][len]true;else break;}for(int i1;im;i){for(int j1;jn;j){// dp[len1][len2] // dp[len1-1][len2] s1[len1-1]s3[len1len2-1]if(s1[i-1]s3[ij-1])dp[i][j]dp[i-1][j];if(s2[j-1]s3[ij-1])dp[i][j]dp[i][j]||dp[i][j-1];}}return dp[m][n];}
};221. 最大正方形⭐
本来应该用三维dp表示正方形右下角的横纵坐标第三维为 以该坐标为右下角的所有全1正方形边长即dp[i][j][k]表示 以 i,j为右下角边长为k的正方形是否存在 dp思想是否存在由子问题的解递推而来如果dp[i-1][j][k-1]dp[i][j-1][k-1]dp[i-1][j-1][k-1]三者都为true则dp[i][j][k]为true
思路来呀
可以优化为两维dp[i][j]的值为int型表示 以该坐标为右下角的所有全1正方形之中最大的边长 比如 边长为3的全1正方形区域那么它一定包含了一个边长为2和边长为1的全1正方形区域。所以我们只需记录以(i, j)为右下角的区域包含的最大全1正方形边长即可这个最大边长也即以(i , j)为右下角的全1正方形的个数
class Solution {
public:
const int N305;int maximalSquare(vectorvectorchar matrix) {int mmatrix.size();int nmatrix[0].size();vectorvectorint dp(m1,vectorint(n1,0));// vectorvectorvectorbool dp(N,vectorvectorbool(N,vectorbool(N,false)));int mx0;for(int i0;im;i)if(matrix[i][0]1)dp[i][0]1,mx1;for(int i0;in;i)if(matrix[0][i]1)dp[0][i]1,mx1;for(int i1;im;i){for(int j1;jn;j){if(matrix[i][j]1){dp[i][j]min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])1;mxmax(mx,dp[i][j]);}}}return mx*mx;}
};
