力扣10.12

2267. 检查是否有合法括号字符串路径

题目链接

一个括号字符串是一个非空且只包含和的字符串。如果下面任意条件为真，那么这个括号字符串就是合法的。'('')'

字符串是。()
字符串可以表示为 （ 连接 ），和都是合法括号序列。AB``A``B``A``B
字符串可以表示为，其中是合法括号序列。(A)A
给你一个的括号网格图矩阵。网格图中一个合法括号路径是满足以下所有条件的一条路径：m x ngrid

路径开始于左上角格子。(0, 0)
路径结束于右下角格子。(m - 1, n - 1)
路径每次只会向下或者向右移动。
路径经过的格子组成的括号字符串是合法的。
如果网格图中存在一条合法括号路径，请返回，否则返回。true``false

数据范围

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 要么是，要么是。'('')'

分析

记忆化搜索+剪枝，dfs传入的参数为当前位置坐标(x,y)和此时左括号和右括号的差值c，只有在终点且c==0才满足条件，有几个优化，首先c不能小于0（否则就说明左括号比右括号少，必然不成立），n+m-1必须为偶数，否则差值不可能为偶数

代码

class Solution {
public:
    const static int N = 105;
    int dp[N][N][N];
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};
    int n, m;
    int dfs(int x, int y, vector<vector<char>>& grid, int c) {
        if(x < 0 || y < 0 || x >= n || y >= m) return 0;
        if(grid[x][y] == '(') c ++ ;
        else c -- ;
        if(c < 0) return 0;
        int &t = dp[x][y][c];
        if(t != -1) return t;
        if(x == n - 1 && y == m - 1) {
            if(c == 0) return t = 1;
            else return t = 0;
        }
        t = 0;
        for(int i = 0; i < 2; i ++ ) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(dfs(nx, ny, grid ,c)) t = 1; 
        }
        return t;
    }
    bool hasValidPath(vector<vector<char>>& grid) {
        n = grid.size();
        m = grid[0].size();
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < m; j ++ ) {
                for(int k = 0; k <= (n + m) / 2; k ++ ) {
                    dp[i][j][k] = -1;
                }
            }
        }
        if((n + m - 1) % 2) return false;
        if(grid[0][0] == ')') return false;
        int res = dfs(0, 0, grid, 0);
        return res;
    }
};

1937. 扣分后的最大得分

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分减少 abs(c1 - c2) 。

请你返回你能得到的最大得分。

abs(x) 定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为-x。

数据范围

m == points.length
n == points[r].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= points[r][c] <= 105

分析

令dp[i][j]表示选择points[i][j]的最大得分，暴力枚举上一行的所有列k，则

$d p [i] [j] = d p [i - 1] [k] + p o in t s [i] [j] - ∣ k - j ∣$
但是这样子时间复杂度为 $O(nm^2)$ ，会超时，得考虑优化
我们去掉绝对值
$dp[i][j]=\begin{cases} points[i][j]+max(dp[i-1][k])-(j-k)，k\le j \\ points[i][j]+max(dp[i-1][k])-(k-j)，k\gt j \end{cases}$

在提出 $j$

$dp[i][j]=\begin{cases} points[i][j] - j +max(dp[i-1][k]) + k)，k\le j \\ points[i][j] + j +max(dp[i-1][k])- k，k\gt j \end{cases}$

此时可以考虑优化了，只要找到一行中 $j$ 左边 $d p [i - 1] [k] + k$ 的最大值和 $j$ 右边 $d p [i - 1] [k] - k$ 的最大值，这个可以用两个一维数组表示，

$ma xx 1 [j]$ 表示 $j$ 左边 $d p [i - 1] [k] + k$ 的最大值
同理可以定义 $ma xx 2 [j]$

这两个数组可以在计算完每行的 $d p [i]$ 进行处理，初始化处理 $ma xx 1 [j] = j ， ma xx 2 [j] = - j$
此时状态转移就变成了这样

$d p [i] [j] = ma x (p o in t s [i] [j] - j + ma xx 1 [j], p o in t s [i] [j] + j + ma xx 2 [j])$

注意：处理maxx2时需要从大到小遍历

代码

typedef long long LL;
class Solution {
public:
    int n, m;
    const static int N = 1e5 + 5;
    LL maxx1[N], maxx2[N];
    LL maxPoints(vector<vector<int>>& points) {
        n = points.size();
        m = points[0].size();
        vector<vector<LL>> dp(n + 1);
        for(int i = 1; i <= n; i ++ ) {
            dp[i].resize(m + 1);
        }
        LL res = 0;
        for(int j = 1; j <= m; j ++ ) {
            maxx1[j] = dp[1][j] + j;
            maxx2[j] = dp[1][j] - j;
        }

        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= m; j ++ ) {
                dp[i][j] = max(points[i - 1][j - 1] - j + maxx1[j], points[i - 1][j - 1] + j + maxx2[j]);
                res = max(res, dp[i][j]);
            }
            LL tmax = LLONG_MIN;
            for(int j = 1; j <= m; j ++

2267. 检查是否有合法括号字符串路径

数据范围

分析

代码

1937. 扣分后的最大得分

数据范围

分析

代码

相关文章

`相关文章`