题目
输入一个 \(m\times n\) 的矩阵 \(grid\)，输出选择任意单元格作为起点，至少移动一次能够得到的最大得分。每次移动只能向正右方和正下方的单元格移动，不必相邻。假设从单元格 \((x_{1},y_{1})\) 移动到 \((x_{2},y_{2})\)，则本次移动的得分为 \(grid[x_{2}][y_{2}]-grid[x_{1}][y_{1}]\)。
数据范围：\(2\leq m,n\leq 1000\)，\(4\leq m\times n\leq 10^{5}\)，\(1\leq grid[i][j]\le 10^{5}\)。
思路
比赛时想到计算过程存在重叠子问题，可以使用记忆化搜索。定义 \(f[i][j]\) 表示以 \((i,j)\) 为起点能够得到的最大得分，初始化 \(f[i][j]\) 为负无穷。当 \(i<m-1\) 且 \(j<n-1\) 时，状态转移方程为 \(f[i][j]=\max{(f[i+1][j]+grid[i+1][j]-grid[i][j],f[i][j+1])+grid[i][j+1]-grid[i][j]}\)。也可以将记忆化搜索转化为自底向上的形式，或者定义 \(f[i][j]\) 表示以 \((i,j)\) 为终点能够得到的最大得分。
通过观察可以发现，对于某个移动路径，得分只和起点和终点有关，中间的值都被抵消了。也就是说，某个起点能够得到的最大得分，是其右下角的最大值减去起点的值，反之亦然。所以也可以定义 \(f[i][j]\) 表示 \((i,j)\) 右下角的最大值或者左上角的最小值，然后进行递推。
时间复杂度为 \(O(mn)\)，空间复杂度为 \(O(mn)\)。灵神题解有个空间复杂度为 \(O(n)\) 的做法，思路是维护每列的最小值。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int maxScore(List<List<Integer>> grid) {
int m = grid.size(), n = grid.get(0).size();
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], Integer.MIN_VALUE);
}
dfs(0, 0, grid, dp);
int ans = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
private int dfs(int x, int y, List<List<Integer>> grid, int[][] dp) {
int m = grid.size(), n = grid.get(0).size();
if (dp[x][y] == Integer.MIN_VALUE) {
if (x + 1 < m) {
int diff = grid.get(x + 1).get(y) - grid.get(x).get(y);
dp[x][y] = Math.max(dp[x][y], diff + dfs(x + 1, y, grid, dp));
}
if (y + 1 < n) {
int diff = grid.get(x).get(y + 1) - grid.get(x).get(y);
dp[x][y] = Math.max(dp[x][y], diff + dfs(x, y + 1, grid, dp));
}
}
return Math.max(0, dp[x][y]);
}
}
|
题目
输入从 \(0\) 到 \(n-1\) 的一个排列 \(nums\)，输出从 \(0\) 到 \(n-1\) 的排列 \(perm\)，使得 \(score(perm)=\sum_{i=0}^{n-1}{|perm[i]-nums[perm[(i+1)\bmod n|}\) 的值最小。如果有多个满足条件的排列，则返回字典序最小的那个。
数据范围：\(2\leq n\leq 14\)。
思路
通过观察可以发现，对于一个给定的排列 \(perm\)，将其循环移动不会改变 \(score(perm)\) 的值。要使满足条件的 \(perm\) 字典序最小，那么必然有 \(perm[0]=0\)。暴力的想法是枚举所有排列，但是时间复杂度为 \(n!\times n\)。由于枚举过程中，存在重复子问题，可以使用记忆化搜索来降低时间复杂度到 \(O(2^{n}n^{2})\)。定义 \(f[mask][pre]\) 表示已经选择集合 \(mask\) 中的数，上一个选择的数是 \(pre\)，剩余的数排列能够得到的最小分数。同理，定义 \(g[mask][pre]\) 表示下一个选择什么数能够使得分数最小，以及相同分数的排列字典序最小。可以看下灵神题解，不使用记忆化搜索，自底向上的解法也是非常经典的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int[] findPermutation(int[] nums) {
int n = nums.length;
int[][] f = new int[1 << n][n];
int[][] g = new int[1 << n][n];
for (int i = 0; i < (1 << n) - 1; i++) {
Arrays.fill(f[i], -1);
}
for (int i = 0; i < n; i++) {
f[(1 << n) - 1][i] = Math.abs(i - nums[0]);
}
dfs(1, 0, nums, f, g);
int[] ans = new int[n];
for (int i = 0, mask = 0, cur = 0; i < n; i++) {
ans[i] = cur;
mask |= 1 << cur;
cur = g[mask][cur];
}
return ans;
}
private int dfs(int mask, int pre, int[] nums, int[][] f, int[][] g) {
int n = nums.length;
if (mask == (1 << n) - 1 || f[mask][pre] != -1) {
return f[mask][pre];
}
int res = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
if ((mask >> i & 1) == 0) {
int cur = dfs(mask | 1 << i, i, nums, f, g) + Math.abs(pre - nums[i]);
if (cur < res) {
res = cur;
g[mask][pre] = i;
}
}
}
return f[mask][pre] = res;
}
}
|