1. 知识点总结

题目	难度	知识点
跳跃游戏	🐸	DP
合并区间	🐸	数组（剪枝）
不同路径	🐸🐸	DP求组合数
最小路径和	🐸🐸	DFS超时，DP

然后经验呢就是一题多解的情况下，还是动点脑子（如果脑子还没罢工的话）用时间复杂度低的保险😋

2. 分题题解

2.1 跳跃游戏

5minAK的下场，就是时间空间复杂度都被按在地上摩擦😅

执行用时：292 ms, 在所有 C++ 提交中击败了6.63%的用户

内存消耗：47.6 MB, 在所有 C++ 提交中击败了8.55%的用户

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //暴力法
        int len=nums.size();
        //初始化
        vector<bool>dp(len);
        fill(dp.begin(),dp.end(),false);
        dp[0]=true;
        //迭代
        for(int i=0;i<len;i++){
            if(dp[i]==false){
                return false;
            }
            for(int j=i+1;j<=min(len-1,i+nums[i]);j++){
                dp[j]=true;
                if(j==len-1){
                    return true;
                }
            }
        }
        return dp[len-1];
    }
};

2.2 合并数组

感谢这题，不然俺都不记得leetcode也可以超时😇

注意排序是必须的，不然可能出现[[2,3],[4,5],[6,7],[8,9],[1,10]]返回结果不是合并的最终结果

以及，if(intervals[j][0]>intervals[i][1]){break;}我认为是比较重要的，也是容易忽视的，忽视的话就是TL

执行用时：44 ms, 在所有 C++ 提交中击败了20.41%的用户

内存消耗：21.1 MB, 在所有 C++ 提交中击败了9.26%的用户

class Solution {
public:
    bool isMerge(vector<int>a,vector<int>b){
        //判断两个集合是否重合
        if(a[0]<=b[1]&&a[0]>=b[0]){
            return true;
        }else if(a[1]<=b[1]&&a[1]>=b[0]){
            return true;
        }else if(b[0]<=a[1]&&b[0]>=a[0]){
            return true;
        }else if(b[1]<=a[1]&&b[1]>=a[0]){
            return true;
        }
        return false;
    }
    vector<int>Merge(vector<int>a,vector<int>b){
        return {min(a[0],b[0]),max(a[1],b[1])};
    }
    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int len=intervals.size();
        vector<bool>vis(len);
        sort(intervals.begin(),intervals.end());
        fill(vis.begin(),vis.end(),false);
        vector<vector<int>>ans;
        for(int i=0;i<len;i++){
            if(vis[i])continue;
            for(int j=i+1;j<len;j++){
                if(intervals[j][0]>intervals[i][1]){
                    break;
                }
                if(!vis[j]&&isMerge(intervals[i],intervals[j])){
                    intervals[i]=Merge(intervals[i],intervals[j]);
                    vis[j]=true;
                }
            }
            vis[i]=true;
            ans.push_back(intervals[i]);
        }
        return ans;
    }
};

2.3 不同路径

dfs超时,然后发现其实这道题目是求C[n][m]的一种变式，所以，回顾一下C[n][m]=C[n-1][m-1]+C[n-1][m]的公式，以及相关初始化C[i][0]=1就可以遍历求啦，需要注意的是整数溢出的问题，这里需要巧用C[n][m]=C[n][n-m]的知识点

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.5 MB, 在所有 C++ 提交中击败了7.45%的用户

planA-DFS超时：

class Solution {
public:
    int ans=0;
    vector<vector<bool> >vis;
    int max_x,max_y;
    void dfs(int x,int y){
        vis[x][y]=true;
        if(x==max_x-1&&y==max_y-1){
            ans++;
        }else{
            if(x+1<max_x&&!vis[x+1][y]){
                dfs(x+1,y);
            }
            if(y+1<max_y&&!vis[x][y+1]){
                dfs(x,y+1);
            }
        }
        vis[x][y]=false;
    }
    int uniquePaths(int m, int n) {
        vis.resize(m);
        max_x=m;
        max_y=n;
        for(int i=0;i<m;i++){
            vis[i].resize(n);
            fill(vis[i].begin(),vis[i].end(),false);
        }
        dfs(0,0);
        return ans;
    }
};

plan-B直接求C，AK：

class Solution {
public:
    int countC(int n,int m){
        vector<vector<int> >C(n+1);
        for(int i=0;i<n+1;i++){
            C[i].resize(m+1);
            fill(C[i].begin(),C[i].end(),0);
            C[i][0]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                C[i][j]=C[i-1][j-1]+C[i-1][j];
            }
        }
        return C[n][m];
    }
    int uniquePaths(int m, int n) {
        //C[m+n,n]
        //排列组合递推公式：C[n,m]=C[n-1,m-1]+C[n-1,m]
        if(n<m){
            return countC(m+n-2,n-1);
        }else{
            return countC(m+n-2,m-1);
        }
    }
};

2.4 最小路径和

DFS暴力的话……超时，好久没有TL了，今天来了两个，好家伙😇

状态转移方程还是很简单哒：dp[i][j]=dp[i][j-1]+grid[i][j];

执行用时：8 ms, 在所有 C++ 提交中击败了77.02%的用户

内存消耗：10 MB, 在所有 C++ 提交中击败了5.36%的用户

planA-dfs:

class Solution {
public:
    int ans=INT_MAX;
    int n,m;
    vector<vector<int> >G;
    void dfs(int x,int y,int sum){
        sum+=G[x][y];
        if(sum>ans)return;
        if(x+1<m){
            dfs(x+1,y,sum);
        }
        if(y+1<n){
            dfs(x,y+1,sum);
        }
        if(x==m-1&&y==n-1){
            ans=min(ans,sum);
        }
    }
    int minPathSum(vector<vector<int>>& grid) {
        //找出一条最短weight的路径
        G=grid;
        m=grid.size();
        n=grid[0].size();
        dfs(0,0,0);
        return ans;
    }
};

planB-DP:

class Solution {
public:
    const int inf=INT_MAX;
    int minPathSum(vector<vector<int>>& grid) {
        //找出一条最短weight的路径
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int> >dp(m);
        for(int i=0;i<m;i++){
            dp[i].resize(n);
            fill(dp[i].begin(),dp[i].end(),inf);
        }
        
        dp[0][0]=grid[0][0];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0){
                    if(j==0){
                        continue;
                    }else{
                        dp[i][j]=dp[i][j-1]+grid[i][j];
                    }
                }else{
                    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];
    }
};