DAY21-动态规划(四)

今天是动态规划的最後一天，整理几题比较复杂的动态规划题目，当作前面几天内容的总结~~直接进例题

例题实战

[887.鸡蛋掉落]（https://leetcode-cn.com/problems/super-egg-drop/）
思路：
一个鸡蛋从k层楼丢下去，只有碎与没碎两种可能
如果有dp[i][j]表示i颗鸡蛋，j层楼的最少次数，可得：
dp[i][j] = max(dp[i][j-t],dp[i-1][t-1]+1)~>将蛋丢在t楼

程序码实现：

[法一] 2Ddp

dp[i][j]表示在有i颗蛋、k层楼的情况下，需要执行的最小次数
则可得 {dp[i][j] = max(dp[i][j-t],dp[i-1][t-1]+1)}~>将蛋丢在t楼
dp[i][j]状态可由dp[i][j-t]->没破，问题简化至i颗蛋，j-t楼，dp[i-1][t-1]->蛋破了，问题简化成i-1颗蛋，t-1楼
而一颗蛋丢下去只有两种状态(破与没破且都要考虑)故dp[i][j]状态可由这两种状态演进而成
由状态转移方程发现在考虑dp[i][j]时，[1~j]都要丢蛋，使得时间复杂度O(KN^2)

[法二] 二分搜寻优化

在变数t的线性搜寻中发现dp[i][j-t]递减的最小值dp[i][0] = 0, dp[i-1][t-1]递增的最大值dp[i-1][j-1]，得两函数在[1~N]有交点
并且两函数会有有序的递增、递减关系，以此用二分搜寻代替线性搜寻

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
        for(int i = 1; i<=k; i++){ 
            for(int j = 1; j<=n; j++){ 
                if(i==1){
                    dp[i][j] = j;
                }
                else{
                    int mmin = INT_MAX;
                    //丢第t层
                    //此处有两种写法(1.线性搜索-->超时 2. 二分搜寻)

                    //1.
                    // for(int t = 1; t<=j; t++){
                    //     int v = max(dp[i][j-t],dp[i-1][t-1])+1;
                    //     mmin = min(v, mmin);
                    // }
                    // dp[i][j] = mmin;

                    // 2.
                    int f = 1, b = j;
                    int mid = -1;
                    while(b>=f){
                        mid = f+(b-f)/2;
                        if(dp[i][j-mid]==dp[i-1][mid-1]){
                            mmin = min(mmin, dp[i-1][mid-1]+1);
                            break;
                        }
                        else if(dp[i-1][mid-1] > dp[i][j-mid]){
                            b = mid-1;
                            mmin = min(mmin, dp[i-1][mid-1]+1);
                        }
                        else if(dp[i-1][mid-1] < dp[i][j-mid]){
                            f = mid+1;
                            mmin = min(mmin, dp[i][j-mid]+1);
                        }                        
                    }
                    dp[i][j] = mmin;
                }
            }
        }
        // for(int i = 1; i<dp.size(); i++){
        //     for(int j = 1; j<dp[0].size(); j++){
        //         cout<< dp[i][j]<<" ";
        //     }
        //     cout<< endl;
        // }
        return dp[k][n];
    }
};

10. 正则表达式匹配
思路:
用dp[i][j]s前 i 个字元是否与 p 中的前 j 个字元匹配
则可得：
一般状况:
dp[i][j] = dp[i-1][j-1] {s[i]=p[j] or p[j-1] == '.'}
遇到*:
dp[i][j] = dp[i-1][j]|dp[i][j-1]|dp[i][j-2]

class Solution {
public:
    bool isMatch(string s, string p) {
        //dp[i][j]为s[1]~str[i]和 p[1]~p[j]
        if (p.empty()) return s.empty();
        vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, 0)); dp[0][0] = 1;
        // 初始化dp[0][j]表示p[1:j]与空串的匹配情况
        for (int j = 1; j <= p.size(); j++) {
            if (p[j-1] != '*') continue;
            else dp[0][j] = dp[0][j-2];
        }
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= p.size(); j++) {
                if (s[i-1] == p[j-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1]; //一般匹配
                else if (p[j-1] == '*') {  //遇到*时的处理
                    dp[i][j] = dp[i][j-2]; //把*当0次
                    if (p[j-2] == '.' || p[j-2] == s[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

329. 矩阵中的最长递增路径
思路：利用空间来记录每一个起点开始的最大路径

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int M = matrix.size(); 
        int N = matrix[0].size(); //matrix不为空
        vector<vector<int> > dp(M, vector<int>(N, -1)); //-1表示未搜索过
        int res = 0;
        int tmp = 0;
        for(int i = 0; i<M; ++i){
            for(int j = 0; j<N; ++j){
                tmp = dfs(matrix, dp, i ,j);
                res = max(res, tmp);
                //cout<< tmp<<" ";
            }
            //cout<< endl;
        }
        return res;
    }
    //fill dp matrix
    int dfs(vector<vector<int> >& matrix, vector<vector<int> >& dp, int x, int y){
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        int res = 1;
        int M = matrix.size(); 
        int N = matrix[0].size(); //matrix不为空
        int travel_lr[] = {1,0,-1,0};
        int travel_td[] = {0,1,0,-1};
        for(int i = 0; i<4; ++i){
            if(x+travel_lr[i]>=M || x+travel_lr[i]<0 || y+travel_td[i]>=N || y+travel_td[i]<0){
                continue;
            }
            if(matrix[x+travel_lr[i]][y+travel_td[i]] < matrix[x][y]){
                res = max(res, dfs(matrix, dp, x+travel_lr[i], y+travel_td[i])+1);
            }
        }
        return dp[x][y] = res;
    }
};