855学习记录算法刷题$Day$-$1$——炎泽汐$de$ Blog

最长有效括号

---

      状态定义为以 i 结尾的最长有效括号长度；

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        if(n == 0 || n == 1){
            return 0;
        }
        int dp[n];
        int ans = 0;
        dp[0] = 0;
        if(s[0] == '(' && s[1] == ')'){
            dp[1] = 2;
            ans = 2;
        }else{
            dp[1] = 0;
        }
        for(int i = 2;i < n;i++){
            if(s[i] == '('){
                dp[i] = 0;
            }else{
                if(dp[i - 2] != 0 && s[i - 1] == '('){
                    dp[i] = dp[i - 2] + 2;
                }else if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){
                    dp[i] = dp[i - 1] + 2;
                    if(i - dp[i - 1] - 2 >= 0 && dp[i - dp[i - 1] - 2] != 0){
                        dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }else{
                    dp[i] = 0;
                }
            }
            if(dp[i] > ans){
                ans = dp[i];
            }
        }
        return ans;
    }
};

接雨水

---

      状态定义为左边最高边和右边最高边；

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0,n = height.size();
        int ldp[n],rdp[n];
        ldp[0] = height[0];
        rdp[n - 1] = height[n - 1];
        for(int i = 1;i < n;i++){
            ldp[i] = max(ldp[i - 1], height[i]);
        }
        for(int i = n - 2;i >= 0;i--){
            rdp[i] = max(rdp[i + 1], height[i]);
        }
        for(int i = 1;i < n - 1;i++){
            sum += max(0, min(ldp[i], rdp[i]) - height[i]);
        }
        return sum;
    }
};

跳跃游戏

---

      状态表示，从 i 出发最远能走到距离；

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int dp = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(dp == 0){
                return false;
            }
            dp = max(dp - 1, nums[i]);
        }
        return true;
    }
};

不同路径

---

      状态表示为到达该格的不同走法数量；

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        if(n == 1 || m == 1){
            return 1;
        }
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0){
                    dp[i][j] = 1;
                }else if(j == 0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        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 - 2] + dp[m - 2][n - 1];
    }
};

最小路径和

---

      状态表示为到达该格的最小路径和；

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        if(m == 1 && n == 1){
            return grid[0][0];
        }
        int dp[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0 && j - 1 >= 0){
                    dp[i][j] = grid[i][j] + dp[i][j - 1];
                }else if(j == 0 && i - 1 >= 0){
                    dp[i][j] = grid[i][j] + dp[i - 1][j];
                }else if(i > 0 && j > 0){
                    dp[i][j] = grid[i][j] + min(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};