dpdpdp

这里写目录标题

- 139. 单词拆分
- 322. 零钱兑换
- 300. 最长递增子序列
- 120. 三角形最小路径和
- 64. 最小路径和
- 63. 不同路径 II
- 5. 最长回文子串（回文dp）⭐
- 97. 交错字符串⭐（抽象成路径问题）
- 221. 最大正方形⭐

139. 单词拆分

class Solution {
public:
    const int N=305;
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(N,false);
        set<string> S;
        S.clear();
        for(int i=0;i<wordDict.size();i++){
            S.insert(wordDict[i]);
        }
        dp[0]=true;
        int n=s.size();
        for(int i=1;i<=n;i++){//从头开始长度为i的子串
            for(int j=0;j<i;j++){
                if(dp[j]){
                    string str=s.substr(j,i-1-(j-1));//0123
                    if(S.find(str)!=S.end()){
                        dp[i]=true;
                    }
                }
            }
            
        }
        return dp[n];
    }
};

322. 零钱兑换

class Solution {
public:
    const int inf=0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,inf);
        // dp[i]表示凑出金额i最少需要的硬币个数
        dp[0]=0;
        int n=coins.size();
        for(int i=1;i<=amount;i++){
            for(int j=0;j<n;j++){
                if(i>=coins[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 inf=0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,inf);
        // dp[i]表示凑出金额i最少需要的硬币个数
        dp[0]=0;
        int n=coins.size();
         for(int j=0;j<n;j++){
            for(int i=coins[j];i<=amount;i++){

                if(i>=coins[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(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+5,1);
        // dp[0]=0;
        int res=1;
        for(int i=0;i<n;i++){//i是上升子序列最后一个元素的下标
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                    res=max(res,dp[i]);
                }
                
            }
        }
        return res;
    }
};

贪心思想，碰到小的元素，尽可能放在前面
最后得到的最长上升子序列，假设存储在d数组中，d数组的演变过程：
来了个更大的元素（大于d[len]), 直接插入在末尾
如果小，找到大于nums[i] 的第一个元素，替换掉

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> d(n+5,1);
        int len=0;
        d[len]=nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]>d[len]){
                d[++len]=nums[i];
            }
            else{//找到第一个大于nums[i]的d[k] 换掉
                int l=0,r=len;
                while(l<r){
                    int mid=(l+r)/2;
                    // if(d[mid]>nums[i])r=mid;
                    // else l=mid+1;找最大
                    // if(d[mid]<nums[i])r=mid;
                    // else l=mid+1;
                    if(d[mid]<nums[i])l=mid+1;
                    else r=mid;
                }
                d[l]=nums[i];
            }
        }
        return len+1;
    }
};

lower_bound,找到大于等于nums[i]的第一个元素

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> d;

        for(int i=0;i<n;i++){
vector<int>::iterator it =lower_bound(d.begin() , d.end() ,nums[i]);
if(it==d.end())d.push_back(nums[i]);
else
 swap(*it,nums[i]);
        }
        return d.size();
    }
};

120. 三角形最小路径和

倒三角形，注意下标

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m=triangle.size();
        // int n=triangle[0].size();
        vector<vector<int> > dp(m,vector<int>(m,0));
        dp[0][0]=triangle[0][0];
        // int res=0x3f3f3f3f;
       int res=2e6+10;
        for(int i=1;i<m;i++){
           
            for(int j=0;j<=i;j++){
                 if(j==0)dp[i][j]=dp[i-1][j]+triangle[i][j];
                 else if(j==i)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(i==m-1)res=min(res,dp[i][j]);怎么放在这儿就不行了why not？？？？？？
            }
            
        }
        //  res=*min_element(dp[m-1].begin(),dp[m-1].end());
    //    res=min(2000010,-10);
    for(int i=0;i<m;i++)res=min(res,dp[m-1][i]);
    return res;
    }
};

64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int j=1;j<n;j++)dp[0][j]=dp[0][j-1]+grid[0][j];
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                if(j==0)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(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        if(!obstacleGrid[0][0])dp[0][0]=1;
        for(int i=1;i<n;i++)if(!obstacleGrid[0][i])dp[0][i]=dp[0][i-1];
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                if(!obstacleGrid[i][j])
                {
                    if(j==0)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 L=s.size();
        vector<vector<bool> > dp(L+1,vector<bool>(L+1,false));
        int maxlen=1;
        int pos=0;
        for(int len=1;len<=L;len++){
            for(int i=0;i+len-1<L;i++){
                int j=i+len-1;
                // dp[i][j]这段是否为回文串
                if(len==1)dp[i][j]=true;
                else{
                    if(s[i]==s[j]){
                        if(len==2||len==3){
                        dp[i][j]=true;
                        }
                        else {
                        dp[i][j]=dp[i+1][j-1];
                        }
                    }
                }
               if(dp[i][j]){
                   if(len>maxlen){
                       maxlen=len;
                       pos=i;
                   }
               } 
            }
        }
        // return s.substr(pos,maxlen);
        string res;
        for(int len=1;len<=L;len++){
            for(int i=0;i+len-1<L;i++){
                int j=i+len-1;
                if(dp[i][j])res=s.substr(i,len);
            }
        }
        return res;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int L=s.size();
        vector<vector<bool> > dp(L+1,vector<bool>(L+1,false));
        for(int i=0;i<L;i++)dp[i][i]=true;
        int pos=0;
        int maxlen=1;
        for(int len=2;len<=L;len++){
            for(int i=0;i+len-1<L;i++){
                int j=i+len-1;
                // dp[i][j]这段是否为回文串
                
               
                    if(s[i]==s[j]){
                        if(len==2||len==3){
                        dp[i][j]=true;
                        }
                        else {
                        dp[i][j]=dp[i+1][j-1];
                        }
                    }
               
               if(dp[i][j]){
                   maxlen=len;
                   pos=i;
               } 
            }
        }
        return s.substr(pos,maxlen);
        // string res;
        // for(int len=1;len<=L;len++){
        //     for(int i=0;i<L;i++){
        //         int j=i+len-1;
        //         if(dp[i][j])res=s.substr(i,len);
        //     }
        // }
        // return res;
    }
};

97. 交错字符串⭐（抽象成路径问题）

s1s2交错组成s3，把s1s2抽象为横纵坐标，s3抽象为向右向下的路径

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size();
        int n=s2.size();
        if(m+n!=s3.size())return false;// "" ,"" ,"a"
        vector <vector<bool> > dp(m+1,vector<bool>(n+1,false));
        // 一些最基础的子问题的初始化处理
        dp[0][0]=true;
        for(int len=1;len<=m;len++){
            if(s1[len-1]==s3[len-1])dp[len][0]=true;
            else break;
        }
        for(int len=1;len<=n;len++){
            if(s2[len-1]==s3[len-1])dp[0][len]=true;
            else break;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                // dp[len1][len2] 
                // dp[len1-1][len2] s1[len1-1]==s3[len1+len2-1]
                if(s1[i-1]==s3[i+j-1])dp[i][j]=dp[i-1][j];
                if(s2[j-1]==s3[i+j-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 N=305;
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        // vector<vector<vector<bool>>> dp(N,vector<vector<bool>>(N,vector<bool>(N,false)));
        int mx=0;
        for(int i=0;i<m;i++)if(matrix[i][0]=='1')dp[i][0]=1,mx=1;
        for(int i=0;i<n;i++)if(matrix[0][i]=='1')dp[0][i]=1,mx=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;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;
                mx=max(mx,dp[i][j]);

                }
            }
        }
        return mx*mx;
    }
};