力扣10.18

1463. 摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

• 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
• 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
• 两个机器人在任意时刻都不能移动到 grid 外面。
• 两个机器人最后都要到达 grid 最底下一行。

数据范围

• rows == grid.length
• cols == grid[i].length
• 2 <= rows, cols <= 70
• 0 <= grid[i][j] <= 100

分析

使用记忆化搜索来解决，令dfs(i,j,k)表示机器人1，2分别从(i,j)和(i,k)处开始到最后一行的樱桃数目最大值，容易得到

• $dfs(i,j,k)=max(dfs(i+1,j-1,k-1),dfs(i+1,j,k-1),dfs(i+1,j+1,k-1),....dfs(i+1,j+1,k+1))$

代码

class Solution {
public:const static int N = 105;int dp[N][N][N];int n, m;int dfs(int i, int j, int k, vector<vector<int>>& grid) {if(i < 0 || i >= n || j < 0 || j >= m || k < 0 || k >= m) return 0;if(i == n) return 0;int& t = dp[i][j][k];if(t != -1) return t;int c;if(j == k) c = grid[i][j];else c = grid[i][j] + grid[i][k];t = 0;for(int z1 = -1; z1 <= 1; z1 ++ ) {for(int z2 = -1; z2 <= 1; z2 ++ ) {t = max(t, dfs(i + 1, j + z1, k + z2, grid));}}t += c;return t;}int cherryPickup(vector<vector<int>>& grid) {n = grid.size();m = grid[0].size();memset(dp, -1, sizeof(dp));return dfs(0, 0, m - 1, grid);}
};

---

3193. 统计逆序对的数目

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对：

• i < j 且 nums[i] > nums[j]

请你返回 [0, 1, 2, ..., n - 1] 的
排列perm 的数目，满足对 所有 的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。

由于答案可能会很大，将它对 109 + 7 取余 后返回。

数据范围

• 2 <= n <= 300
• 1 <= requirements.length <= n
• requirements[i] = [endi, cnti]
• 0 <= endi <= n - 1
• 0 <= cnti <= 400
• 输入保证至少有一个 i 满足 endi == n - 1 。
• 输入保证所有的 endi 互不相同。

分析

记忆化收缩，令dfs(i,j)表示perm[0]到perm[i]的逆序对数量为j的排列个数，首先对req数组进行预处理，若在i处没有逆序对要求，则将其req设为-1，否则设为对应的值，接下来分两种情况讨论

• 若i-1处req[i-1]>=0(有要求)：$dfs(i,j)=dfs(i,j)+=dfs(i-1,req[i-1])$
• 若i-1处req[i-1]==-1(无要求)：$dfs(i,j)+={\sum }_{k=0}^{min(i,j)}dfs(i-1,j-k),$k为因为第i个数增加的逆序对个数
  对于dfs函数，若传入参数一样，则接下来的过程也一样，这就是为什么能用记忆化搜索优化的原理，这样保证所有的状态都只计算一遍
  接下来考虑剪纸
• 对有要求的情况，
  • 由于前面只有i-1个数，因此若增加第i个数，也只能增加至多i-1个逆序对(第i个数比前面的数都小)，若$req[i-1]+i-1<j$(此时无论如何都到达不了j个逆序对的状态)，此时可以直接返回0
  • 若$j<req[i-1]$(当前逆序对比前一个状态还少)，也是不合法的，返回0
    最后递归边界就是dfs(0,0)=1(0长度0个逆序对的排列个数只有空集)
    代码还附加了递推的写法

代码

typedef long long LL;
class Solution {
public:const static int N = 405, mod = 1e9 + 7;LL dp[N][N]; // 前i个出现j个逆序对int req[N];LL dfs(int x, int cnt) {if(x == 0 && cnt == 0) return  dp[x][cnt] = 1;LL &t = dp[x][cnt];if(t != -1) return t;t = 0;if(x >= 1 && req[x - 1] >= 0) {if(req[x - 1] + x - 1 < cnt || cnt < req[x - 1]) return t = 0;t += dfs(x - 1, req[x - 1]);} else {for(int i = 0; i <= min(x, cnt); i ++ ) {if(x >= 1) t += dfs(x - 1, cnt - i);t %= mod;}   }t %= mod;return t;}LL numberOfPermutations(int n, vector<vector<int>>& requirements) {memset(req, -1, sizeof(req));// memset(dp, -1, sizeof(dp));int maxx = 0;for(auto k : requirements) {req[k[0]] = k[1];maxx = max(maxx, k[1]);}dp[0][0] = 1;for(int i = 1; i < n; i ++ ) {for(int j = 0; j <= maxx; j ++ ) {if(req[i - 1] >= 0) {if(req[i - 1] + i < j || req[i - 1] > j) {dp[i][j] = 0;continue;}dp[i][j] += dp[i - 1][req[i - 1]];dp[i][j] %= mod;} else {for(int k = 0; k <= min(i, j); k ++ ) {dp[i][j] += dp[i - 1][j - k];dp[i][j] %= mod;}}}}return dp[n - 1][maxx];// return dfs(n, maxx);}
};