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，则

• $dp[i][j]=dp[i-1][k]+points[i][j]-|k-j|$
  但是这样子时间复杂度为$O(n{m}^2)$，会超时，得考虑优化
  我们去掉绝对值
• $dp[i][j]=\{\begin{array}{l}points[i][j]+max(dp[i-1][k])-(j-k)，k\le j\\ points[i][j]+max(dp[i-1][k])-(k-j)，k>j\end{array}$

在提出$j$

• $dp[i][j]=\{\begin{array}{l}points[i][j]-j+max(dp[i-1][k])+k)，k\le j\\ points[i][j]+j+max(dp[i-1][k])-k，k>j\end{array}$

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

• $maxx1[j]$表示$j$左边$dp[i-1][k]+k$的最大值
• 同理可以定义$maxx2[j]$

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

• $dp[i][j]=max(points[i][j]-j+maxx1[j],points[i][j]+j+maxx2[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 ++ ) {tmax = max(tmax, dp[i][j] + j);maxx1[j] = tmax;}tmax = LLONG_MIN;for(int j = m; j >= 1; j -- ) {tmax = max(tmax, dp[i][j] - j);maxx2[j] = tmax;}}return res;}};