给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
登录s = 'abcde'，在旋转一次之后结果就是'bcdea' 。
示例 1:
输入: s = "abcde", goal = "cdeab" 输出: true
示例 2:
输入: s = "abcde", goal = "abced" 输出: false
提示:
1 <= s.length, goal.length <= 100s 和 goal 由小写英文字母组成例如 $s=\texttt{abcde}$，旋转一次变成 $\texttt{bcdea}$，再旋转一次变成 $\texttt{cdeab}$。旋转后的字符串是 $s$ 的后缀加上 $s$ 的前缀，例如 $\texttt{cdeab} = \texttt{cde} + \texttt{ab}$。于是构造 $s+s = \texttt{abcdeabcde}$，这个字符串的任意长为 $n$ 的子串，都是 $s$ 的后缀加上 $s$ 的前缀。所以无论 $s$ 如何旋转，旋转后的字符串一定是 $s+s$ 的子串。
于是问题等价于：
注意题目没有保证 $s$ 和 $\textit{goal}$ 长度相等，如果不等，直接返回 $\texttt{false}$。
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
return len(s) == len(goal) and goal in s + s
class Solution {
public boolean rotateString(String s, String goal) {
return s.length() == goal.length() && (s + s).contains(goal);
}
}
class Solution {
public:
bool rotateString(string s, string goal) {
return s.size() == goal.size() && (s + s).contains(goal);
}
};
func rotateString(s, goal string) bool {
return len(s) == len(goal) && strings.Contains(s+s, goal)
}
用 KMP、Z 函数、字符串哈希等算法，都可以 $\mathcal{O}(n)$ 判断 $s+s$ 是否包含 $\textit{goal}$。
下面用的 KMP 算法，原理见 KMP 算法讲解。
# 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
# 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
def kmp_search(text: str, pattern: str) -> List[int]:
m = len(pattern)
pi = [0] * m
cnt = 0
for i in range(1, m):
b = pattern[i]
while cnt and pattern[cnt] != b:
cnt = pi[cnt - 1]
if pattern[cnt] == b:
cnt += 1
pi[i] = cnt
pos = []
cnt = 0
for i, b in enumerate(text):
while cnt and pattern[cnt] != b:
cnt = pi[cnt - 1]
if pattern[cnt] == b:
cnt += 1
if cnt == len(pattern):
pos.append(i - m + 1)
cnt = pi[cnt - 1]
return pos
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
return len(s) == len(goal) and len(kmp_search(s + s, goal)) > 0
class Solution {
public boolean rotateString(String s, String goal) {
return s.length() == goal.length() &&
!kmpSearch((s + s).toCharArray(), goal.toCharArray()).isEmpty();
}
// 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
// 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
private List<Integer> kmpSearch(char[] text, char[] pattern) {
int m = pattern.length;
int[] pi = new int[m];
int cnt = 0;
for (int i = 1; i < m; i++) {
char b = pattern[i];
while (cnt > 0 && pattern[cnt] != b) {
cnt = pi[cnt - 1];
}
if (pattern[cnt] == b) {
cnt++;
}
pi[i] = cnt;
}
List<Integer> pos = new ArrayList<>();
cnt = 0;
for (int i = 0; i < text.length; i++) {
char b = text[i];
while (cnt > 0 && pattern[cnt] != b) {
cnt = pi[cnt - 1];
}
if (pattern[cnt] == b) {
cnt++;
}
if (cnt == m) {
pos.add(i - m + 1);
cnt = pi[cnt - 1];
}
}
return pos;
}
}
class Solution {
// 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
// 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
vector<int> kmp_search(const string& text, const string& pattern) {
int m = pattern.size();
vector<int> pi(m);
int cnt = 0;
for (int i = 1; i < m; i++) {
char b = pattern[i];
while (cnt && pattern[cnt] != b) {
cnt = pi[cnt - 1];
}
if (pattern[cnt] == b) {
cnt++;
}
pi[i] = cnt;
}
vector<int> pos;
cnt = 0;
for (int i = 0; i < text.size(); i++) {
char b = text[i];
while (cnt && pattern[cnt] != b) {
cnt = pi[cnt - 1];
}
if (pattern[cnt] == b) {
cnt++;
}
if (cnt == m) {
pos.push_back(i - m + 1);
cnt = pi[cnt - 1];
}
}
return pos;
}
public:
bool rotateString(string s, string goal) {
return s.size() == goal.size() && !kmp_search(s + s, goal).empty();
}
};
// 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
// 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
func kmpSearch(text, pattern string) (pos []int) {
m := len(pattern)
pi := make([]int, m)
cnt := 0
for i := 1; i < m; i++ {
b := pattern[i]
for cnt > 0 && pattern[cnt] != b {
cnt = pi[cnt-1]
}
if pattern[cnt] == b {
cnt++
}
pi[i] = cnt
}
cnt = 0
for i, b := range text {
for cnt > 0 && pattern[cnt] != byte(b) {
cnt = pi[cnt-1]
}
if pattern[cnt] == byte(b) {
cnt++
}
if cnt == m {
pos = append(pos, i-m+1)
cnt = pi[cnt-1]
}
}
return
}
func rotateString(s, goal string) bool {
return len(s) == len(goal) && kmpSearch(s+s, goal) != nil
}
见下面字符串题单的「一、KMP」。
欢迎关注 B站@灵茶山艾府
由于每次旋转操作都是将最左侧字符移动到最右侧，因此如果 goal 可由 s 经过多步旋转而来，那么 goal 必然会出现在 s + s 中，即满足 (s + s).contains(goal)，同时为了 s 本身过长导致的结果成立，我们需要先确保两字符串长度相等。
代码：
###Java
class Solution {
public boolean rotateString(String s, String goal) {
return s.length() == goal.length() && (s + s).contains(goal);
}
}
contains 操作的复杂度说明看到不少同学对 contains 的复杂度写成 $O(n)$ 有疑问。
在 Java 中，contains 实际最终是通过 indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) 来拿到子串在原串的下标，通过判断下标是否为 $-1$ 来得知子串是否在原串出现过。
我们知道一个较为普通的子串匹配算法的复杂度通为 $O(n*k)$，其中 $n$ 和 $k$ 分别是原串和子串的长度，而一些复杂度上较为优秀的算法可以做到 $O(n + k)$，例如 KMP。
从复杂度上来看 KMP 似乎要更好，但实际上对于 indexOf 这一高频操作而言，KMP 的预处理逻辑和空间开销都是不可接受的。
因此在 OpenJDK 中的 indexOf 源码中，你看不到诸如 KMP 这一类「最坏情况下仍为线性复杂度」的算法实现。
但是 contains 的复杂度真的就是 $O(n * k)$ 吗？
其实并不是，这取决于 JVM 是否有针对 indexOf 的优化，在最为流行 HotSpot VM 中，就有对 indexOf 的优化。
使用以下两行命令执行 Main.java，会得到不同的用时。
###Java
// Main.java
import java.util.*;
class Main {
static String ss = "1900216589537958049456207450268985232242852754963049829410964867980510717200606495004259179775210762723370289106970649635773837906542900276476226929871813370344374628795427969854262816333971458418647697497933767559786473164055741512717436542961770628985635269208255141092673831132865";
static String pp = "830411595466023844647269831101019568881117264597716557501027220546437084223034983361631430958163646150071031688420479928498493050624766427709034028819288384316713084883575266906600102801186671777455503932259958027055697399984336592981698127456301551509241";
static int cnt = (int) 1e8;
static public void main(String[] args) {
long start = System.currentTimeMillis();
while (cnt-- > 0) ss.contains(pp);
System.out.println(System.currentTimeMillis() - start);
}
}
环境说明：
###Shell
➜ java -version
java version "1.8.0_131"
Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.131-b11, mixed mode)
先执行 javac Main.java 进行编译后：
indexOf 实现进行匹配（执行多次，平均耗时为基准值 $X$）：java -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_indexOf Main
indexOf 进行匹配（执行多次，平均耗时为基准值 $X$ 的 $[0.55, 0.65]$ 之间）：java Main
因此实际运行的 contains 操作的复杂度为多少并不好确定，但可以确定是要优于 $O(n * k)$ 的。
今日份加餐 :【面试高频题】难度 2/5，结合二分的序列 DP 运用题 🍭🍭🍭🍭
或是考虑加练如下「模拟」题 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 6. Z 字形变换 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 8. 字符串转换整数 (atoi) | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 12. 整数转罗马数字 | LeetCode 题解链接 | 中等 | 🤩🤩 |
| 59. 螺旋矩阵 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 65. 有效数字 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 73. 矩阵置零 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 89. 格雷编码 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 166. 分数到小数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 414. 第三大的数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 419. 甲板上的战舰 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 443. 压缩字符串 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 457. 环形数组是否存在循环 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 528. 按权重随机选择 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 539. 最小时间差 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 726. 原子的数量 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
思路
首先，如果 $s$ 和 $\textit{goal}$ 的长度不一样，那么无论怎么旋转，$s$ 都不能得到 $\textit{goal}$，返回 $\text{false}$。在长度一样（都为 $n$）的前提下，假设 $s$ 旋转 $i$ 位，则与 $\textit{goal}$ 中的某一位字符 $\textit{goal}[j]$ 对应的原 $s$ 中的字符应该为 $s[(i+j) \bmod n]$。在固定 $i$ 的情况下，遍历所有 $j$，若对应字符都相同，则返回 $\text{true}$。否则，继续遍历其他候选的 $i$。若所有的 $i$ 都不能使 $s$ 变成 $\textit{goal}$，则返回 $\text{false}$。
代码
###Python
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
m, n = len(s), len(goal)
if m != n:
return False
for i in range(n):
for j in range(n):
if s[(i + j) % n] != goal[j]:
break
else:
return True
return False
###Java
class Solution {
public boolean rotateString(String s, String goal) {
int m = s.length(), n = goal.length();
if (m != n) {
return false;
}
for (int i = 0; i < n; i++) {
boolean flag = true;
for (int j = 0; j < n; j++) {
if (s.charAt((i + j) % n) != goal.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
}
###C#
public class Solution {
public bool rotateString(string s, string goal) {
int m = s.Length, n = goal.Length;
if (m != n) {
return false;
}
for (int i = 0; i < n; i++) {
bool flag = true;
for (int j = 0; j < n; j++) {
if (s[(i + j) % n] != goal[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
}
###C++
class Solution {
public:
bool rotateString(string s, string goal) {
int m = s.size(), n = goal.size();
if (m != n) {
return false;
}
for (int i = 0; i < n; i++) {
bool flag = true;
for (int j = 0; j < n; j++) {
if (s[(i + j) % n] != goal[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
};
###C
bool rotateString(char * s, char * goal){
int m = strlen(s), n = strlen(goal);
if (m != n) {
return false;
}
for (int i = 0; i < n; i++) {
bool flag = true;
for (int j = 0; j < n; j++) {
if (s[(i + j) % n] != goal[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
###JavaScript
var rotateString = function(s, goal) {
const m = s.length, n = goal.length;
if (m !== n) {
return false;
}
for (let i = 0; i < n; i++) {
let flag = true;
for (let j = 0; j < n; j++) {
if (s[(i + j) % n] !== goal[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
};
###go
func rotateString(s, goal string) bool {
n := len(s)
if n != len(goal) {
return false
}
next:
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if s[(i+j)%n] != goal[j] {
continue next
}
}
return true
}
return false
}
复杂度分析
时间复杂度：$O(n^2)$，其中 $n$ 是字符串 $s$ 的长度。我们需要双重循环来判断。
空间复杂度：$O(1)$。仅使用常数空间。
思路
首先，如果 $s$ 和 $\textit{goal}$ 的长度不一样，那么无论怎么旋转，$s$ 都不能得到 $\textit{goal}$，返回 $\text{false}$。字符串 $s + s$ 包含了所有 $s$ 可以通过旋转操作得到的字符串，只需要检查 $\textit{goal}$ 是否为 $s + s$ 的子字符串即可。具体可以参考「28. 实现 strStr() 的官方题解」的实现代码，本题解中采用直接调用库函数的方法。
代码
###Python
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
return len(s) == len(goal) and goal in s + s
###Java
class Solution {
public boolean rotateString(String s, String goal) {
return s.length() == goal.length() && (s + s).contains(goal);
}
}
###C#
public class Solution {
public bool rotateString(string s, string goal) {
return s.Length == goal.Length && (s + s).Contains(goal);
}
}
###C++
class Solution {
public:
bool rotateString(string s, string goal) {
return s.size() == goal.size() && (s + s).find(goal) != string::npos;
}
};
###C
bool rotateString(char * s, char * goal){
int m = strlen(s), n = strlen(goal);
if (m != n) {
return false;
}
char * str = (char *)malloc(sizeof(char) * (m + n + 1));
sprintf(str, "%s%s", goal, goal);
return strstr(str, s) != NULL;
}
###JavaScript
var rotateString = function(s, goal) {
return s.length === goal.length && (s + s).indexOf(goal) !== -1;
};
###go
func rotateString(s, goal string) bool {
return len(s) == len(goal) && strings.Contains(s+s, goal)
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。$\text{KMP}$ 算法搜索子字符串的时间复杂度为 $O(n)$，其他搜索子字符串的方法会略有差异。
空间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。$\text{KMP}$ 算法搜索子字符串的空间复杂度为 $O(n)$，其他搜索子字符串的方法会略有差异。
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：
输入: 10 输出: 4 解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。 注意 1 和 10 不是好数, 因为他们在旋转之后不变。
提示：
[1, 10000]。利用 $n$ 的范围为 $1e4$，我们可以直接检查 $[1, n]$ 的每个数。
由于每一个位数都需要翻转，因此如果当前枚举到的数值 x 中包含非有效翻转数字（非 0125689）则必然不是好数；而在每一位均为有效数字的前提下，若当前枚举到的数值 x 中包含翻转后能够发生数值上变化的数值（2569），则为好数。
代码：
###Java
class Solution {
public int rotatedDigits(int n) {
int ans = 0;
out:for (int i = 1; i <= n; i++) {
boolean ok = false;
int x = i;
while (x != 0) {
int t = x % 10;
x /= 10;
if (t == 2 || t == 5 || t == 6 || t == 9) ok = true;
else if (t != 0 && t != 1 && t != 8) continue out;
}
if (ok) ans++;
}
return ans;
}
}
###TypeScript
function rotatedDigits(n: number): number {
let ans = 0
out:for (let i = 1; i <= n; i++) {
let ok = false
let x = i
while (x != 0) {
const t = x % 10
x = Math.floor(x / 10)
if (t == 2 || t == 5 || t == 6 || t == 9) ok = true
else if (t != 0 && t != 1 && t != 8) continue out
}
if (ok) ans++
}
return ans
};
###Python3
class Solution:
def rotatedDigits(self, n: int) -> int:
ans = 0
for i in range(1, n + 1):
ok, x = False, i
while x != 0:
t = x % 10
x = x // 10
if t == 2 or t == 5 or t == 6 or t == 9:
ok = True
elif t != 0 and t != 1 and t != 8:
ok = False
break
ans = ans + 1 if ok else ans
return ans
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
视频讲解，从 19:30 开始（基于题目 2376. 统计特殊整数）。
讲了数位 DP 的通用模板，以及如何使用该模板秒杀相关困难题目。
讲完题目后还讲了一些上分的训练技巧。
根据题意，好数中不能有 $3,4,7$，且至少包含 $2,5,6,9$ 中的一个。
将 $n$ 转换成字符串 $s$，定义 $f(i,\textit{hasDiff}, \textit{isLimit}, \textit{isNum})$ 表示构造从左往右第 $i$ 位及其之后数位的合法方案数，其余参数的含义为：
后面两个参数可适用于其它数位 DP 题目。
枚举要填入的数字，具体实现逻辑见代码。对于本题来说，由于前导零对答案无影响，$\textit{isNum}$ 可以省略。
下面代码中 Java/C++/Go 只需要记忆化 $(i,\textit{hasDiff})$ 这个状态，因为：
!isLimit 成立时才去记忆化。接着上面的例子，在前面填 $12$ 的时候，下一位填的数字不能超过 $3$，因此算出来的结果是不能套用到前面填的是 $10,11$ 这些数字上面的。DIFFS = (0, 0, 1, -1, -1, 1, 1, -1, 0, 1)
class Solution:
def rotatedDigits(self, n: int) -> int:
s = str(n)
@cache
def f(i: int, has_diff: bool, is_limit: bool) -> int:
if i == len(s):
return has_diff # 只有包含 2/5/6/9 才算一个好数
res = 0
up = int(s[i]) if is_limit else 9
for d in range(0, up + 1): # 枚举要填入的数字 d
if DIFFS[d] != -1: # d 不是 3/4/7
res += f(i + 1, has_diff or DIFFS[d], is_limit and d == up)
return res
return f(0, False, True)
class Solution {
private static int[] DIFFS = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
public int rotatedDigits(int n) {
char[] s = Integer.toString(n).toCharArray();
int[][] memo = new int[s.length][2];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(0, 0, true, s, memo);
}
private int dfs(int i, int hasDiff, boolean isLimit, char[] s, int[][] memo) {
if (i == s.length) {
return hasDiff; // 只有包含 2/5/6/9 才算一个好数
}
if (!isLimit && memo[i][hasDiff] >= 0) {
return memo[i][hasDiff];
}
int res = 0;
int up = isLimit ? s[i] - '0' : 9;
for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
if (DIFFS[d] != -1) { // d 不是 3/4/7
res += dfs(i + 1, hasDiff | DIFFS[d], isLimit && d == up, s, memo);
}
}
if (!isLimit) {
memo[i][hasDiff] = res;
}
return res;
}
}
int diffs[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
class Solution {
public:
int rotatedDigits(int n) {
string s = to_string(n);
int m = s.size();
vector<array<int, 2>> memo(m, {-1, -1});
auto dfs = [&](this auto&& dfs, int i, bool has_diff, bool is_limit) -> int {
if (i == m) {
return has_diff; // 只有包含 2/5/6/9 才算一个好数
}
if (!is_limit && memo[i][has_diff] >= 0) {
return memo[i][has_diff];
}
int res = 0;
int up = is_limit ? s[i] - '0' : 9;
for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
if (diffs[d] != -1) { // d 不是 3/4/7
res += dfs(i + 1, has_diff || diffs[d], is_limit && d == up);
}
}
if (!is_limit) {
memo[i][has_diff] = res;
}
return res;
};
return dfs(0, false, true);
}
};
var diffs = [10]int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1}
func rotatedDigits(n int) int {
s := strconv.Itoa(n)
m := len(s)
memo := make([][2]int, m)
for i := range memo {
memo[i] = [2]int{-1, -1}
}
var dfs func(int, int, bool) int
dfs = func(i, isDiff int, isLimit bool) (res int) {
if i == m {
return isDiff // 只有包含 2/5/6/9 才算一个好数
}
if !isLimit {
p := &memo[i][isDiff]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
up := 9
if isLimit {
up = int(s[i] - '0')
}
for d := 0; d <= up; d++ { // 枚举要填入的数字 d
if diffs[d] != -1 { // d 不是 3/4/7
res += dfs(i+1, isDiff|diffs[d], isLimit && d == up)
}
}
return
}
return dfs(0, 0, true)
}
见下面动态规划题单的「十、数位 DP」。
欢迎关注 B站@灵茶山艾府
动归数组d，d[i]表示数字i的状态。
d[i]对应有三个值，1是好数，0是普数，-1是坏数。
好数是旋转后不同的数比如(2,5,6,9)，普数是旋转以后相同的数如(0,1,8)，坏数是旋转后不能成立的数如(3,4,7)，这里前十个数的好坏情况通过切片给预处理了。
某数字i末位或末位以外的数字为坏数，数字i就肯定是坏数，例如(897,389,941)等等。
如果数字i不是坏数，那只要末位或末位以外的数字存在好数，那数字i就肯定是好数，如(120,886,509)等等就是好数，如(808,880)就是普数，程序这里计算用了按位或"|"。
如果数字i的结果d[i]是1是好数，那总答案就加1。
主要是末位以外的数字在计算该数字前肯定计算过了，所以可以动归。
class Solution:
def rotatedDigits(self, N: int) -> int:
ans = 0
d = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] + [0] * (N - 9)
for i in range(N + 1):
if d[i // 10] == -1 or d[i % 10] == -1:
d[i] = -1
elif d[i // 10] == 1 or d[i % 10] == 1:
d[i] = 1
ans += 1
return ans
class Solution:
def rotatedDigits(self, N: int) -> int:
ans, d = 0, [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] + [0] * (N - 9)
for i in range(N + 1):
d[i] = -1 in (d[i // 10], d[i % 10]) and -1 or d[i // 10] | d[i % 10]
ans += d[i] == 1
return ans
func rotatedDigits(N int) int {
ans, d := 0, make([]int, N + 1)
copy(d, []int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1})
for i := 0; i <= N; i++ {
if d[i / 10] == -1 || d[i % 10] == -1 {
d[i] = -1
} else if d[i] = d[i / 10] | d[i % 10]; d[i] == 1 {
ans++
}
}
return ans
}
impl Solution {
pub fn rotated_digits(n: i32) -> i32 {
let mut d: Vec<i32> = vec![0, 0, 1, -1, -1, 1, 1, -1, 0, 1];
d.extend(vec![0; (n - 9).max(0) as usize]);
let mut ans = 0;
for i in 0..=n as usize {
d[i] = if d[i / 10] == -1 || d[i % 10] == -1 {-1} else {d[i / 10] | d[i % 10]};
ans += if d[i] == 1 {1} else {0};
}
ans
}
}
var rotatedDigits = function(N) {
let ans = 0
const d = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1].concat(Array(Math.max(0, N - 9)).fill(0))
for (let i = 0; i <= N; ++i) {
if (d[Math.floor(i / 10)] == -1 || d[i % 10] == -1) {
d[i] = -1
} else if (d[Math.floor(i / 10)] == 1 || d[i % 10] == 1) {
d[i] = 1
++ans
}
}
return ans
};
function rotatedDigits(N: number): number {
let ans: number = 0;
let d: number[] = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1, ...Array(Math.max(N - 9, 0)).fill(0)];
for (let i of Array.from({length: N + 1}, (_, k) => k)) {
let [j, k] = [Math.trunc(i / 10), i % 10];
d[i] = (d[j] == -1 || d[k] == -1) && -1 || d[j] | d[k];
ans += Number(d[i] == 1);
}
return ans
};
py
go
rs
js
ts
为方便描述，本文把 $\textit{nums}$ 简称为 $a$。
如果分别计算 $F(0),F(1),\ldots,F(n-1)$，总的时间复杂度是 $\mathcal{O}(n^2)$，太慢了。
考察相邻两项的差值，能否加快计算过程？
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2)
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3)
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4)
从 $F(0)$ 到 $F(1)$，$a_0,a_1,a_2,a_3$ 的系数是怎么变的？
所以 $F(1) = F(0) + a_0+a_1+a_2-3a_3 = F(0) + (a_0+a_1+a_2+a_3)-4a_3$。
这意味着，如果已知 $F(0)$ 以及 $a$ 的总和 $S$，就可以 $\mathcal{O}(1)$ 算出
$$
F(1) = F(0) + S - n\cdot a_{n-1}
$$
从 $F(1)$ 到 $F(2)$，$a_0,a_1,a_2,a_3$ 的系数是怎么变的？
所以有
$$
F(2) = F(1) + S - n\cdot a_{n-2}
$$
一般地，从 $F(i-1)$ 到 $F(i)$：
所以有
$$
F(i) = F(i-1) + S - n\cdot a_{n-i}
$$
根据上式，我们可以先算出 $F(0)$，然后从 $F(0)$ 开始，递推算出 $F(1),F(2),\ldots,F(n-1)$。
答案为所有 $F(i)$ 的最大值。
class Solution:
def maxRotateFunction(self, nums: list[int]) -> int:
n = len(nums)
f = sum(i * x for i, x in enumerate(nums)) # F(0)
s = sum(nums) # nums 的总和
ans = f
for i in range(n - 1, 0, -1):
f += s - n * nums[i]
ans = max(ans, f)
return ans
class Solution {
public int maxRotateFunction(int[] nums) {
int n = nums.length;
int f = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
f += i * nums[i]; // 计算 F(0)
sum += nums[i]; // 计算 nums 的总和
}
int ans = f;
for (int i = n - 1; i > 0; i--) {
f += sum - n * nums[i];
ans = Math.max(ans, f);
}
return ans;
}
}
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
int n = nums.size();
int f = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
f += i * nums[i]; // 计算 F(0)
sum += nums[i]; // 计算 nums 的总和
}
int ans = f;
for (int i = n - 1; i > 0; i--) {
f += sum - n * nums[i];
ans = max(ans, f);
}
return ans;
}
};
int maxRotateFunction(int* nums, int numsSize) {
int f = 0;
int sum = 0;
for (int i = 0; i < numsSize; i++) {
f += i * nums[i]; // 计算 F(0)
sum += nums[i]; // 计算 nums 的总和
}
int ans = f;
for (int i = numsSize - 1; i > 0; i--) {
f += sum - numsSize * nums[i];
ans = MAX(ans, f);
}
return ans;
}
func maxRotateFunction(nums []int) int {
n := len(nums)
f := 0
sum := 0
for i, x := range nums {
f += i * x // 计算 F(0)
sum += x // 计算 nums 的总和
}
ans := f
for i := n - 1; i > 0; i-- {
f += sum - n*nums[i]
ans = max(ans, f)
}
return ans
}
var maxRotateFunction = function(nums) {
const n = nums.length;
let f = 0;
let sum = 0;
for (let i = 0; i < n; i++) {
f += i * nums[i]; // 计算 F(0)
sum += nums[i]; // 计算 nums 的总和
}
let ans = f;
for (let i = n - 1; i > 0; i--) {
f += sum - n * nums[i];
ans = Math.max(ans, f);
}
return ans;
};
impl Solution {
pub fn max_rotate_function(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut f = 0;
let mut sum = 0;
for (i, &x) in nums.iter().enumerate() {
f += i as i32 * x; // 计算 F(0)
sum += x; // 计算 nums 的总和
}
let mut ans = f;
for i in (1..n).rev() {
f += sum - n as i32 * nums[i];
ans = ans.max(f);
}
ans
}
}
欢迎关注 B站@灵茶山艾府
给定一个长度为 n 的整数数组 nums 。
假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 F 为：
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]返回 F(0), F(1), ..., F(n-1)中的最大值 。
生成的测试用例让答案符合 32 位 整数。
示例 1:
输入: nums = [4,3,2,6] 输出: 26 解释: F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
示例 2:
输入: nums = [100] 输出: 0
提示:
n == nums.length1 <= n <= 105-100 <= nums[i] <= 100为了方便，我们将 $nums$ 的长度记为 $n$。
题目要对「旋转数组」做逻辑，容易想到将 $nums$ 进行复制拼接，得到长度为 $2 * n$ 的新数组，在新数组上任意一个长度为 $n$ 的滑动窗口都对应了一个旋转数组。
然后考虑在窗口的滑动过程中，计算结果会如何变化，假设当前我们处理到下标为 $[i, i + n - 1]$ 的滑动窗口，根据题意，当前结果为：
$$
cur = nums[i] * 0 + nums[i + 1] * 1 + ... + nums[i + n - 1] * (n - 1)
$$
当窗口往后移动一位，也就是窗口的右端点来到 $i + n$ 的位置，左端点来到 $i + 1$ 的位置。
我们需要增加「新右端点」的值，即增加 $nums[i + n] * (n - 1)$，同时减去「旧左端点」的值，即减少 $nums[i] * 0$（固定为 $0$），然后更新新旧窗口的公共部分 $[i + 1, i + n - 1]$。
不难发现，随着窗口的逐步右移，每一位公共部分的权值系数都会进行减一。
$$
nums[i + 1] * 1 + nums[i + 2] * 2 + ... + nums[i + n - 1] * (n - 1)
$$
变为
$$
nums[i + 1] * 0 + nums[i + 2] * 1 + ... + nums[i + n - 1] * (n - 2)
$$
因此，公共部分的差值为 $\sum_{idx = i + 1}^{i + n - 1}nums[idx]$，这引导我们可以使用前缀和进行优化。
至此，我们从旧窗口到新窗口的过渡，都是 $O(1)$，整体复杂度为 $O(n)$。
实现上，我们并不需要真正对 $nums$ 进行复制拼接，而只需要在计算前缀和数组 $sum$ 进行简单的下标处理即可。
代码：
###Java
class Solution {
public int maxRotateFunction(int[] nums) {
int n = nums.length;
int[] sum = new int[n * 2 + 10];
for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
int ans = 0;
for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
for (int i = n + 1, cur = ans; i < 2 * n; i++) {
cur += nums[(i - 1) % n] * (n - 1);
cur -= sum[i - 1] - sum[i - n];
if (cur > ans) ans = cur;
}
return ans;
}
}
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
思路
记数组 $\textit{nums}$ 的元素之和为 $\textit{numSum}$。根据公式，可以得到：
更一般地，当 $1 \le k \lt n$ 时，$F(k) = F(k-1) + \textit{numSum} - n \times \textit{nums}[n-k]$。我们可以不停迭代计算出不同的 $F(k)$，并求出最大值。
代码
###Python
class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
f, n, numSum = 0, len(nums), sum(nums)
for i, num in enumerate(nums):
f += i * num
res = f
for i in range(n - 1, 0, -1):
f = f + numSum - n * nums[i]
res = max(res, f)
return res
###Java
class Solution {
public int maxRotateFunction(int[] nums) {
int f = 0, n = nums.length, numSum = Arrays.stream(nums).sum();
for (int i = 0; i < n; i++) {
f += i * nums[i];
}
int res = f;
for (int i = n - 1; i > 0; i--) {
f += numSum - n * nums[i];
res = Math.max(res, f);
}
return res;
}
}
###C#
public class Solution {
public int MaxRotateFunction(int[] nums) {
int f = 0, n = nums.Length, numSum = nums.Sum();
for (int i = 0; i < n; i++) {
f += i * nums[i];
}
int res = f;
for (int i = n - 1; i > 0; i--) {
f += numSum - n * nums[i];
res = Math.Max(res, f);
}
return res;
}
}
###C++
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
int f = 0, n = nums.size();
int numSum = accumulate(nums.begin(), nums.end(), 0);
for (int i = 0; i < n; i++) {
f += i * nums[i];
}
int res = f;
for (int i = n - 1; i > 0; i--) {
f += numSum - n * nums[i];
res = max(res, f);
}
return res;
}
};
###C
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int maxRotateFunction(int* nums, int numsSize){
int f = 0, numSum = 0;
for (int i = 0; i < numsSize; i++) {
f += i * nums[i];
numSum += nums[i];
}
int res = f;
for (int i = numsSize - 1; i > 0; i--) {
f += numSum - numsSize * nums[i];
res = MAX(res, f);
}
return res;
}
###JavaScript
var maxRotateFunction = function(nums) {
let f = 0, n = nums.length, numSum = _.sum(nums);
for (let i = 0; i < n; i++) {
f += i * nums[i];
}
let res = f;
for (let i = n - 1; i > 0; i--) {
f += numSum - n * nums[i];
res = Math.max(res, f);
}
return res;
};
###go
func maxRotateFunction(nums []int) int {
numSum := 0
for _, v := range nums {
numSum += v
}
f := 0
for i, num := range nums {
f += i * num
}
ans := f
for i := len(nums) - 1; i > 0; i-- {
f += numSum - len(nums)*nums[i]
ans = max(ans, f)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。计算 $\textit{numSum}$ 需要 $O(n)$ 时间，计算初始值 $F(0)$ 也需要 $O(n)$ 时间，因为我们只需遍历一次数组。之后，我们进行 $n - 1$ 次迭代来计算 $F(k)$ 的其余值。每次迭代使用递推关系式更新值：
$$
F(k) = F(k-1) + \textit{numSum} - n \cdot \textit{nums}[n-k]
$$
此更新仅涉及常数数量的算术运算，因此每次迭代的时间复杂度为 $O(1)$。因此，总的时间复杂度为：
$$
O(n) + O(n) + O(n) = O(n)
$$
总体而言，该算法的时间复杂度为线性。
空间复杂度：$O(1)$。仅使用常数空间。
推导过程：
（1）F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-2) * Bk[n-2] + (n-1) * Bk[n-1]
（2）F(k+1) = 0 * Bk[n-1] + 1 * Bk[0] + 2 * Bk[2] + ... + (n-1) * Bk[n-2]
（2）-（1）得：F(k+1) - F(k) = (Bk[0] + Bk[1] + ... + Bk[n-2]) - (n-1)*Bk[n-1]
可得：F(k+1) - F(k) = (Bk[0] + Bk[1] + ... + Bk[n-2] + Bk[n-1]) - n*Bk[n-1]
令S=Sum{Bk}
有：F(k+1) = F(k) + S - n * Bk[n-1]
###cpp
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
long N = A.size();
long S = 0;
long t = 0;
for (int i = 0; i < N; ++i) {
S += A[i];
t += i * A[i];
}
long res = t;
for (int i = N - 1; i >= 0; --i) {
// F(k+1) = F(k) + S - n * Bk[n-1]
t += S - N * (long)A[i];
res = max(res, t);
}
return res;
}
};
思路与算法
题目要求我们在总花费不超过 $k$ 的情况下，找到一条从 $\textit{grid}[0][0]$ 到 $\textit{grid}[m-1][n-1]$ 的路径，使得获得的分数最大。这种有限制的最优化问题结构类似背包问题，可以用动态规划解决。
定义状态 $\textit{dp}[i][j][c]$ 表示到达位置 $(i,j)$，当前花费为 $c$ 时的最大得分。
我们从当前格子向后转移，即从 $(i,j)$ 出发，可以向下或向右移动，将下一个格子的代价和分数加入：
状态转移为：
$$
\begin{aligned}
\textit{dp}[i+1][j][c + \textit{cost}(i+1,j)] &= \max(\textit{dp}[i+1][j][c + \textit{cost}(i+1,j)],\textit{dp}[i][j][c] + \textit{grid}[i+1][j]) \
\textit{dp}[i][j+1][c + \textit{cost}(i,j+1)] &= \max(\textit{dp}[i][j+1][c + \textit{cost}(i,j+1)],\textit{dp}[i][j][c] + \textit{grid}[i][j+1])
\end{aligned}
$$
其中：
$$
\textit{cost}(i,j) =
\begin{cases}
1, & \textit{grid}[i][j] \neq 0 \
0, & \textit{grid}[i][j] = 0
\end{cases}
$$
初始状态为 $\textit{dp}[0][0][0] = 0$（起点不计入得分和花费）。
最终答案为：
$$
\max\limits_{0 \le c \le k} \textit{dp}[m-1][n-1][c]
$$
代码
###C++
class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int k) {
int m = grid.size();
int n = grid[0].size();
vector<vector<vector<int>>> dp(
m, vector<vector<int>>(n, vector<int>(k + 1, INT_MIN)));
dp[0][0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int c = 0; c <= k; c++) {
if (dp[i][j][c] == INT_MIN)
continue;
if (i + 1 < m) {
int val = grid[i + 1][j];
int cost = (val == 0 ? 0 : 1);
if (c + cost <= k) {
dp[i + 1][j][c + cost] =
max(dp[i + 1][j][c + cost], dp[i][j][c] + val);
}
}
if (j + 1 < n) {
int val = grid[i][j + 1];
int cost = (val == 0 ? 0 : 1);
if (c + cost <= k) {
dp[i][j + 1][c + cost] =
max(dp[i][j + 1][c + cost], dp[i][j][c] + val);
}
}
}
}
}
int ans = INT_MIN;
for (int c = 0; c <= k; c++) {
ans = max(ans, dp[m - 1][n - 1][c]);
}
return ans < 0 ? -1 : ans;
}
};
###Java
class Solution {
public int maxPathScore(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int[][][] dp = new int[m][n][k + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], Integer.MIN_VALUE);
}
}
dp[0][0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int c = 0; c <= k; c++) {
if (dp[i][j][c] == Integer.MIN_VALUE) continue;
if (i + 1 < m) {
int val = grid[i + 1][j];
int cost = (val == 0 ? 0 : 1);
if (c + cost <= k) {
dp[i + 1][j][c + cost] = Math.max(
dp[i + 1][j][c + cost],
dp[i][j][c] + val
);
}
}
if (j + 1 < n) {
int val = grid[i][j + 1];
int cost = (val == 0 ? 0 : 1);
if (c + cost <= k) {
dp[i][j + 1][c + cost] = Math.max(
dp[i][j + 1][c + cost],
dp[i][j][c] + val
);
}
}
}
}
}
int ans = Integer.MIN_VALUE;
for (int c = 0; c <= k; c++) {
ans = Math.max(ans, dp[m - 1][n - 1][c]);
}
return ans < 0 ? -1 : ans;
}
}
###Python3
class Solution:
def maxPathScore(self, grid, k):
m, n = len(grid), len(grid[0])
INF = float('-inf')
dp = [[[INF] * (k + 1) for _ in range(n)] for _ in range(m)]
dp[0][0][0] = 0
for i in range(m):
for j in range(n):
for c in range(k + 1):
if dp[i][j][c] == INF:
continue
if i + 1 < m:
val = grid[i + 1][j]
cost = 0 if val == 0 else 1
if c + cost <= k:
dp[i + 1][j][c + cost] = max(
dp[i + 1][j][c + cost],
dp[i][j][c] + val
)
if j + 1 < n:
val = grid[i][j + 1]
cost = 0 if val == 0 else 1
if c + cost <= k:
dp[i][j + 1][c + cost] = max(
dp[i][j + 1][c + cost],
dp[i][j][c] + val
)
ans = max(dp[m - 1][n - 1])
return -1 if ans < 0 else ans
###C
int maxPathScore(int** grid, int m, int* gridColSize, int k) {
int n = gridColSize[0];
int*** dp = (int***)malloc(m * sizeof(int**));
for (int i = 0; i < m; i++) {
dp[i] = (int**)malloc(n * sizeof(int*));
for (int j = 0; j < n; j++) {
dp[i][j] = (int*)malloc((k + 1) * sizeof(int));
for (int c = 0; c <= k; c++) {
dp[i][j][c] = INT_MIN;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int c = 0; c <= k; c++) {
if (dp[i][j][c] == INT_MIN) continue;
if (i + 1 < m) {
int val = grid[i + 1][j];
int cost = val == 0 ? 0 : 1;
if (c + cost <= k) {
int* target = &dp[i + 1][j][c + cost];
if (*target < dp[i][j][c] + val)
*target = dp[i][j][c] + val;
}
}
if (j + 1 < n) {
int val = grid[i][j + 1];
int cost = val == 0 ? 0 : 1;
if (c + cost <= k) {
int* target = &dp[i][j + 1][c + cost];
if (*target < dp[i][j][c] + val)
*target = dp[i][j][c] + val;
}
}
}
}
}
int ans = INT_MIN;
for (int c = 0; c <= k; c++) {
if (dp[m - 1][n - 1][c] > ans)
ans = dp[m - 1][n - 1][c];
}
return ans < 0 ? -1 : ans;
}
###Golang
func maxPathScore(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
const INF = math.MinInt32
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, k+1)
for c := range dp[i][j] {
dp[i][j][c] = INF
}
}
}
dp[0][0][0] = 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for c := 0; c <= k; c++ {
if dp[i][j][c] == INF {
continue
}
if i+1 < m {
val := grid[i+1][j]
cost := 0
if val != 0 {
cost = 1
}
if c+cost <= k {
if dp[i+1][j][c+cost] < dp[i][j][c]+val {
dp[i+1][j][c+cost] = dp[i][j][c] + val
}
}
}
if j+1 < n {
val := grid[i][j+1]
cost := 0
if val != 0 {
cost = 1
}
if c+cost <= k {
if dp[i][j+1][c+cost] < dp[i][j][c]+val {
dp[i][j+1][c+cost] = dp[i][j][c] + val
}
}
}
}
}
}
ans := INF
for c := 0; c <= k; c++ {
if dp[m-1][n-1][c] > ans {
ans = dp[m-1][n-1][c]
}
}
if ans < 0 {
return -1
}
return ans
}
###C#
public class Solution {
public int MaxPathScore(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[,,] dp = new int[m, n, k + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int c = 0; c <= k; c++)
dp[i, j, c] = int.MinValue;
dp[0, 0, 0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int c = 0; c <= k; c++) {
if (dp[i, j, c] == int.MinValue) continue;
if (i + 1 < m) {
int val = grid[i + 1][j];
int cost = val == 0 ? 0 : 1;
if (c + cost <= k) {
dp[i + 1, j, c + cost] = Math.Max(
dp[i + 1, j, c + cost],
dp[i, j, c] + val
);
}
}
if (j + 1 < n) {
int val = grid[i][j + 1];
int cost = val == 0 ? 0 : 1;
if (c + cost <= k) {
dp[i, j + 1, c + cost] = Math.Max(
dp[i, j + 1, c + cost],
dp[i, j, c] + val
);
}
}
}
}
}
int ans = int.MinValue;
for (int c = 0; c <= k; c++) {
ans = Math.Max(ans, dp[m - 1, n - 1, c]);
}
return ans < 0 ? -1 : ans;
}
}
###JavaScript
var maxPathScore = function(grid, k) {
const m = grid.length, n = grid[0].length;
const INF = -Infinity;
const dp = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(k + 1).fill(INF))
);
dp[0][0][0] = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let c = 0; c <= k; c++) {
if (dp[i][j][c] === INF) continue;
if (i + 1 < m) {
const val = grid[i + 1][j];
const cost = val === 0 ? 0 : 1;
if (c + cost <= k) {
dp[i + 1][j][c + cost] = Math.max(
dp[i + 1][j][c + cost],
dp[i][j][c] + val
);
}
}
if (j + 1 < n) {
const val = grid[i][j + 1];
const cost = val === 0 ? 0 : 1;
if (c + cost <= k) {
dp[i][j + 1][c + cost] = Math.max(
dp[i][j + 1][c + cost],
dp[i][j][c] + val
);
}
}
}
}
}
let ans = Math.max(...dp[m - 1][n - 1]);
return ans < 0 ? -1 : ans;
};
###TypeScript
function maxPathScore(grid: number[][], k: number): number {
const m = grid.length, n = grid[0].length;
const INF = -Infinity;
const dp: number[][][] = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(k + 1).fill(INF))
);
dp[0][0][0] = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let c = 0; c <= k; c++) {
if (dp[i][j][c] === INF) continue;
if (i + 1 < m) {
const val = grid[i + 1][j];
const cost = val === 0 ? 0 : 1;
if (c + cost <= k) {
dp[i + 1][j][c + cost] = Math.max(
dp[i + 1][j][c + cost],
dp[i][j][c] + val
);
}
}
if (j + 1 < n) {
const val = grid[i][j + 1];
const cost = val === 0 ? 0 : 1;
if (c + cost <= k) {
dp[i][j + 1][c + cost] = Math.max(
dp[i][j + 1][c + cost],
dp[i][j][c] + val
);
}
}
}
}
}
const ans = Math.max(...dp[m - 1][n - 1]);
return ans < 0 ? -1 : ans;
}
###Rust
impl Solution {
pub fn max_path_score(grid: Vec<Vec<i32>>, k: i32) -> i32 {
let m = grid.len();
let n = grid[0].len();
let k = k as usize;
let inf = i32::MIN / 2;
let mut dp = vec![vec![vec![inf; k + 1]; n]; m];
dp[0][0][0] = 0;
for i in 0..m {
for j in 0..n {
for c in 0..=k {
if dp[i][j][c] == inf {
continue;
}
if i + 1 < m {
let val = grid[i + 1][j];
let cost = if val == 0 { 0 } else { 1 };
if c + cost <= k {
dp[i + 1][j][c + cost] =
dp[i + 1][j][c + cost].max(dp[i][j][c] + val);
}
}
if j + 1 < n {
let val = grid[i][j + 1];
let cost = if val == 0 { 0 } else { 1 };
if c + cost <= k {
dp[i][j + 1][c + cost] =
dp[i][j + 1][c + cost].max(dp[i][j][c] + val);
}
}
}
}
}
let mut ans = inf;
for c in 0..=k {
ans = ans.max(dp[m - 1][n - 1][c]);
}
if ans < 0 { -1 } else { ans }
}
}
复杂度分析
给你一个 m x n 的网格 grid，其中每个单元格包含以下值之一：0、1 或 2。另给你一个整数 k。
你从左上角 (0, 0) 出发，目标是到达右下角 (m - 1, n - 1)，只能向 右 或 下 移动。
每个单元格根据其值对路径有以下贡献：
0 的单元格：分数增加 0，花费 0。1 的单元格：分数增加 1，花费 1。2 的单元格：分数增加 2，花费 1。返回在总花费不超过 k 的情况下可以获得的 最大分数 ，如果不存在有效路径，则返回 -1。
注意： 如果到达最后一个单元格时总花费超过 k，则该路径无效。
示例 1：
输入： grid = [[0, 1],[2, 0]], k = 1
输出： 2
解释：
最佳路径为：
| 单元格 | grid[i][j] | 当前分数 | 累计分数 | 当前花费 | 累计花费 |
|---|---|---|---|---|---|
| (0, 0) | 0 | 0 | 0 | 0 | 0 |
| (1, 0) | 2 | 2 | 2 | 1 | 1 |
| (1, 1) | 0 | 0 | 2 | 0 | 1 |
因此，可获得的最大分数为 2。
示例 2：
输入： grid = [[0, 1],[1, 2]], k = 1
输出： -1
解释：
不存在在总花费不超过 k 的情况下到达单元格 (1, 1) 的路径，因此答案是 -1。
提示：
1 <= m, n <= 2000 <= k <= 103grid[0][0] == 00 <= grid[i][j] <= 2由于每次只能向右或者向下移动，对于每个值为 $0$ 的单元格花费 $0$，对于每个值为 $1$ 的单元格花费 $1$，因此对于网格中的每个单元格，到达该单元格的路径的最大分数需要通过到达相邻单元格的路径的最大分数与花费计算得到。可以使用动态规划计算最大分数。
网格 $\textit{grid}$ 的网格 $\textit{coins}$ 的大小是 $m \times n$。创建 $m \times n \times (k + 1)$ 的三维数组 $\textit{dp}$，其中 $\textit{dp}[i][j][c]$ 表示从单元格 $(0, 0)$ 到达单元格 $(i, j)$ 且花费不超过 $c$ 的最大分数，对于不可能的状态使用 $-\infty$ 表示。由于花费一定非负，因此为方便处理，规定当 $c < 0$ 时 $\textit{dp}[i][j][c] = -\infty$，表示不可能的状态。
当 $i = 0$ 且 $j = 0$ 时，路径上只有 $(0, 0)$ 一个位置，根据 $\textit{grid}[0][0] = 0$ 可以得到分数是 $0$ 且花费是 $0$，因此动态规划的边界情况是：对于任意 $0 \le c \le k$，$\textit{dp}[0][0][c] = 0$。
当 $i > 0$ 或 $j > 0$ 时，计算 $\textit{dp}[i][j][c]$ 需要考虑到达相邻单元格的路径的最大分数与花费。定义示性函数 $\mathbb{I}(b)$，当 $b = \text{true}$ 时 $\mathbb{I}(b) = 1$，当 $b = \text{false}$ 时 $\mathbb{I}(b) = 0$。
当 $i = 0$ 且 $j > 0$ 时，只能从 $(i, j - 1)$ 向右移动到 $(i, j)$，因此 $\textit{dp}[i][j][c] = \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[0][j] \ne 0)] + \textit{grid}[i][j]$。
当 $i > 0$ 且 $j = 0$ 时，只能从 $(i - 1, j)$ 向下移动到 $(i, j)$，因此 $\textit{dp}[i][j][c] = \textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][0] \ne 0)] + \textit{grid}[i][j]$。
当 $i > 0$ 且 $j > 0$ 时，可以从 $(i - 1, j)$ 向下移动到 $(i, j)$ 或从 $(i, j - 1)$ 向右移动到 $(i, j)$，到达 $(i, j)$ 的路径的最大分数为其中的最大值，因此 $\textit{dp}[i][j][c] = \max(\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)], \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)]) + \textit{grid}[i][j])$。
根据上述分析，当 $i > 0$ 或 $j > 0$ 时，动态规划的状态转移方程如下。
$$
\textit{dp}[i][j][c] = \begin{cases}
\textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[0][j] \ne 0)] + \textit{grid}[i][j], & i = 0 \wedge j > 0 \
\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][0] \ne 0)] + \textit{grid}[i][j], & i > 0 \wedge j = 0 \
\max(\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)], \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)]) + \textit{grid}[i][j]), & i > 0 \wedge j > 0
\end{cases}
$$
根据动态规划的状态转移方程，计算 $\textit{dp}[i][j]$ 的顺序可以是以下两种。
从小到大遍历每个 $i$，对于每个 $i$ 从小到大遍历每个 $j$。该顺序为按行遍历。
从小到大遍历每个 $j$，对于每个 $j$ 从小到大遍历每个 $i$。该顺序为按列遍历。
计算得到 $\textit{dp}[m - 1][n - 1][k]$ 即为从左上角到右下角的总花费不超过 $k$ 的最大分数。
上述做法的时间复杂度和空间复杂度都是 $O(mnk)$。
实现方面可以优化空间，按行遍历和按列遍历的优化空间做法分别如下。
按行遍历时，由于 $\textit{dp}[i][]$ 只取决于 $\textit{dp}[i - 1][]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一行的状态，将空间复杂度降到 $O(n)$。
按列遍历时，由于 $\textit{dp}[][j]$ 只取决于 $\textit{dp}[][j - 1]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一列的状态，将空间复杂度降到 $O(m)$。
使用优化空间做法时，对于每个单元格 $(i, j)$ 计算状态值时应从大到小遍历每个 $c$。
当 $m \ge n$ 时可以使用按行遍历，当 $m < n$ 时可以使用按列遍历，将空间复杂度降到 $O(\min(m, n) \times k)$。
下面的代码为不优化空间的实现。
###Java
class Solution {
public int maxPathScore(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][][] dp = new int[m][n][k + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], Integer.MIN_VALUE);
}
}
Arrays.fill(dp[0][0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[0][j][c] = dp[0][j - 1][c - costIncrease] + grid[0][j];
}
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][0][c] = dp[i - 1][0][c - costIncrease] + grid[i][0];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][j][c] = Math.max(dp[i - 1][j][c - costIncrease], dp[i][j - 1][c - costIncrease]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1][k] >= 0 ? dp[m - 1][n - 1][k] : -1;
}
}
###C#
public class Solution {
public int MaxPathScore(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][][] dp = new int[m][][];
for (int i = 0; i < m; i++) {
dp[i] = new int[n][];
for (int j = 0; j < n; j++) {
dp[i][j] = new int[k + 1];
Array.Fill(dp[i][j], int.MinValue);
}
}
Array.Fill(dp[0][0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[0][j][c] = dp[0][j - 1][c - costIncrease] + grid[0][j];
}
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][0][c] = dp[i - 1][0][c - costIncrease] + grid[i][0];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][j][c] = Math.Max(dp[i - 1][j][c - costIncrease], dp[i][j - 1][c - costIncrease]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1][k] >= 0 ? dp[m - 1][n - 1][k] : -1;
}
}
下面的代码为优化空间的实现。
###Java
class Solution {
public int maxPathScore(int[][] grid, int k) {
return grid.length >= grid[0].length ? maxPathScoreHorizontal(grid, k) : maxPathScoreVertical(grid, k);
}
public int maxPathScoreHorizontal(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[n][k + 1];
for (int j = 0; j < n; j++) {
Arrays.fill(dp[j], Integer.MIN_VALUE);
}
Arrays.fill(dp[0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? dp[j - 1][c - costIncrease] + grid[0][j] : Integer.MIN_VALUE;
}
}
for (int i = 1; i < m; i++) {
int costIncrease0 = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[i][0] : Integer.MIN_VALUE;
}
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? Math.max(dp[j][c - costIncrease], dp[j - 1][c - costIncrease]) + grid[i][j] : Integer.MIN_VALUE;
}
}
}
return dp[n - 1][k] >= 0 ? dp[n - 1][k] : -1;
}
public int maxPathScoreVertical(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][k + 1];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], Integer.MIN_VALUE);
}
Arrays.fill(dp[0], 0);
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? dp[i - 1][c - costIncrease] + grid[i][0] : Integer.MIN_VALUE;
}
}
for (int j = 1; j < n; j++) {
int costIncrease0 = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[0][j] : Integer.MIN_VALUE;
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? Math.max(dp[i][c - costIncrease], dp[i - 1][c - costIncrease]) + grid[i][j] : Integer.MIN_VALUE;
}
}
}
return dp[m - 1][k] >= 0 ? dp[m - 1][k] : -1;
}
}
###C#
public class Solution {
public int MaxPathScore(int[][] grid, int k) {
return grid.Length >= grid[0].Length ? MaxPathScoreHorizontal(grid, k) : MaxPathScoreVertical(grid, k);
}
public int MaxPathScoreHorizontal(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][] dp = new int[n][];
for (int j = 0; j < n; j++) {
dp[j] = new int[k + 1];
Array.Fill(dp[j], int.MinValue);
}
Array.Fill(dp[0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? dp[j - 1][c - costIncrease] + grid[0][j] : int.MinValue;
}
}
for (int i = 1; i < m; i++) {
int costIncrease0 = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[i][0] : int.MinValue;
}
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? Math.Max(dp[j][c - costIncrease], dp[j - 1][c - costIncrease]) + grid[i][j] : int.MinValue;
}
}
}
return dp[n - 1][k] >= 0 ? dp[n - 1][k] : -1;
}
public int MaxPathScoreVertical(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) {
dp[i] = new int[k + 1];
Array.Fill(dp[i], int.MinValue);
}
Array.Fill(dp[0], 0);
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? dp[i - 1][c - costIncrease] + grid[i][0] : int.MinValue;
}
}
for (int j = 1; j < n; j++) {
int costIncrease0 = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[0][j] : int.MinValue;
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? Math.Max(dp[i][c - costIncrease], dp[i - 1][c - costIncrease]) + grid[i][j] : int.MinValue;
}
}
}
return dp[m - 1][k] >= 0 ? dp[m - 1][k] : -1;
}
}
时间复杂度：$O(mnk)$，其中 $m$ 和 $n$ 分别是网格 $\textit{grid}$ 的行数和列数，$k$ 是总花费上限。动态规划的状态数是 $O(mnk)$，每个状态的计算时间是 $O(1)$，因此时间复杂度是 $O(mnk)$。
空间复杂度：$O(mnk)$ 或 $O(\min(m, n) \times k)$，其中 $m$ 和 $n$ 分别是网格 $\textit{grid}$ 的行数和列数，$k$ 是总花费上限。空间复杂度取决于实现方式，不优化空间的实现需要创建大小为 $m \times n \times (k + 1)$ 的三维数组因此空间复杂度是 $O(mnk)$，优化空间的实现需要创建大小为 $\min(m, n) \times (k + 1)$ 的二维数组因此空间复杂度是 $O(\min(m, n) \times k)$。
做法类似 3418. 机器人可以获得的最大金币数，我的题解。
和 3418 题一样，定义 $\textit{dfs}(i,j,k)$ 表示从 $(0,0)$ 走到 $(i,j)$，在总花费不超过 $k$ 的情况下，可以获得的最大分数。
两种情况取最大值，得
$$
\textit{dfs}(i,j,k) = \max(\textit{dfs}(i-1, j, k'), \textit{dfs}(i, j-1, k')) + x
$$
递归边界：
递归入口：$\textit{dfs}(m-1,n-1,k)$，这是原问题，也是答案。
原理见 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，包含把记忆化搜索 1:1 翻译成递推的技巧。
本题视频讲解，欢迎点赞关注~
###py
# 手写 max 更快
max = lambda a, b: b if b > a else a
class Solution:
def maxPathScore(self, grid: List[List[int]], k: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i < 0 or j < 0 or k < 0: # 出界或者总花费超了
return -inf
if i == 0 and j == 0:
return 0 # 题目保证 grid[0][0] = 0
x = grid[i][j]
if x > 0:
k -= 1
return max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x
ans = dfs(len(grid) - 1, len(grid[0]) - 1, k)
dfs.cache_clear() # 避免超出内存限制
return -1 if ans < 0 else ans
###java
class Solution {
public int maxPathScore(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int[][][] memo = new int[m][n][k + 1];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1);
}
}
int ans = dfs(m - 1, n - 1, k, grid, memo);
return ans < 0 ? -1 : ans;
}
private int dfs(int i, int j, int k, int[][] grid, int[][][] memo) {
if (i < 0 || j < 0 || k < 0) { // 出界或者总花费超了
return Integer.MIN_VALUE;
}
if (i == 0 && j == 0) {
return 0; // 题目保证 grid[0][0] = 0
}
if (memo[i][j][k] != -1) {
return memo[i][j][k];
}
int x = grid[i][j];
int newK = x > 0 ? k - 1 : k;
return memo[i][j][k] = Math.max(dfs(i - 1, j, newK, grid, memo), dfs(i, j - 1, newK, grid, memo)) + x;
}
}
###cpp
class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector memo(m, vector(n, vector<int>(k + 1, -1)));
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i < 0 || j < 0 || k < 0) { // 出界或者总花费超了
return INT_MIN;
}
if (i == 0 && j == 0) {
return 0; // 题目保证 grid[0][0] = 0
}
int& res = memo[i][j][k];
if (res != -1) {
return res;
}
int x = grid[i][j];
if (x > 0) {
k--;
}
return res = max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x;
};
int ans = dfs(m - 1, n - 1, k);
return ans < 0 ? -1 : ans;
}
};
###go
func maxPathScore(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
memo := make([][][]int, m)
for i := range memo {
memo[i] = make([][]int, n)
for j := range memo[i] {
memo[i][j] = make([]int, k+1)
for p := range memo[i][j] {
memo[i][j][p] = -1
}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 || k < 0 { // 出界或者总花费超了
return math.MinInt
}
if i == 0 && j == 0 {
return 0 // 题目保证 grid[0][0] = 0
}
p := &memo[i][j][k]
if *p != -1 {
return *p
}
x := grid[i][j]
if x > 0 {
k--
}
res := max(dfs(i-1, j, k), dfs(i, j-1, k)) + x
*p = res
return res
}
ans := dfs(m-1, n-1, k)
if ans < 0 {
return -1
}
return ans
}
把 $f[0][1]$（或者 $f[1][0]$）除了首项都初始化成 $0$，这样 $f[1][1]$ 可以用递推式计算，无需特判。
###py
# 手写 max 更快
max = lambda a, b: b if b > a else a
class Solution:
def maxPathScore(self, grid: List[List[int]], K: int) -> int:
m, n = len(grid), len(grid[0])
f = [[[-inf] * (K + 2) for _ in range(n + 1)] for _ in range(m + 1)]
f[0][1][1:] = [0] * (K + 1)
for i, row in enumerate(grid):
for j, x in enumerate(row):
for k in range(K + 1):
new_k = k - 1 if x else k
f[i + 1][j + 1][k + 1] = max(f[i][j + 1][new_k + 1], f[i + 1][j][new_k + 1]) + x
ans = f[m][n][-1]
return -1 if ans < 0 else ans
###java
class Solution {
public int maxPathScore(int[][] grid, int K) {
int m = grid.length;
int n = grid[0].length;
int[][][] f = new int[m + 1][n + 1][K + 2];
for (int[][] mat : f) {
for (int[] row : mat) {
Arrays.fill(row, Integer.MIN_VALUE);
}
}
Arrays.fill(f[0][1], 1, K + 2, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = grid[i][j];
for (int k = 0; k <= K; k++) {
int newK = x > 0 ? k - 1 : k;
f[i + 1][j + 1][k + 1] = Math.max(f[i][j + 1][newK + 1], f[i + 1][j][newK + 1]) + x;
}
}
}
int ans = f[m][n][K + 1];
return ans < 0 ? -1 : ans;
}
}
###cpp
class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int K) {
int m = grid.size(), n = grid[0].size();
vector f(m + 1, vector(n + 1, vector<int>(K + 2, INT_MIN)));
ranges::fill(f[0][1].begin() + 1, f[0][1].end(), 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = grid[i][j];
for (int k = 0; k <= K; k++) {
int new_k = k - (x > 0);
f[i + 1][j + 1][k + 1] = max(f[i][j + 1][new_k + 1], f[i + 1][j][new_k + 1]) + x;
}
}
}
int ans = f[m][n][K + 1];
return ans < 0 ? -1 : ans;
}
};
###go
func maxPathScore(grid [][]int, K int) int {
m, n := len(grid), len(grid[0])
f := make([][][]int, m+1)
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, K+2)
for k := range f[i][j] {
f[i][j][k] = math.MinInt
}
}
}
for k := 1; k < K+2; k++ {
f[0][1][k] = 0
}
for i, row := range grid {
for j, x := range row {
for k := range K + 1 {
newK := k
if x > 0 {
newK--
}
f[i+1][j+1][k+1] = max(f[i][j+1][newK+1], f[i+1][j][newK+1]) + x
}
}
}
ans := f[m][n][K+1]
if ans < 0 {
return -1
}
return ans
}
去掉第一个维度。
为了避免覆盖状态 $f[i][j+1][\textit{newK}+1]$，$k$ 要倒序枚举（类似 0-1 背包）。
###py
# 手写 max 更快
max = lambda a, b: b if b > a else a
class Solution:
def maxPathScore(self, grid: List[List[int]], K: int) -> int:
n = len(grid[0])
f = [[-inf] * (K + 2) for _ in range(n + 1)]
f[1][1:] = [0] * (K + 1)
for row in grid:
for j, x in enumerate(row):
for k in range(K, -1, -1):
new_k = k - 1 if x else k
f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x
ans = f[n][-1]
return -1 if ans < 0 else ans
###java
class Solution {
public int maxPathScore(int[][] grid, int K) {
int n = grid[0].length;
int[][] f = new int[n + 1][K + 2];
for (int[] row : f) {
Arrays.fill(row, Integer.MIN_VALUE);
}
Arrays.fill(f[1], 1, K + 2, 0);
for (int[] row : grid) {
for (int j = 0; j < n; j++) {
int x = row[j];
for (int k = K; k >= 0; k--) {
int newK = x > 0 ? k - 1 : k;
f[j + 1][k + 1] = Math.max(f[j + 1][newK + 1], f[j][newK + 1]) + x;
}
}
}
int ans = f[n][K + 1];
return ans < 0 ? -1 : ans;
}
}
###cpp
class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int K) {
int n = grid[0].size();
vector f(n + 1, vector<int>(K + 2, INT_MIN));
ranges::fill(f[1].begin() + 1, f[1].end(), 0);
for (auto& row : grid) {
for (int j = 0; j < n; j++) {
int x = row[j];
for (int k = K; k >= 0; k--) {
int new_k = k - (x > 0);
f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x;
}
}
}
int ans = f[n][K + 1];
return ans < 0 ? -1 : ans;
}
};
###go
func maxPathScore(grid [][]int, K int) int {
n := len(grid[0])
f := make([][]int, n+1)
for j := range f {
f[j] = make([]int, K+2)
for k := range f[j] {
f[j][k] = math.MinInt
}
}
for k := 1; k < K+2; k++ {
f[1][k] = 0
}
for _, row := range grid {
for j, x := range row {
for k := K; k >= 0; k-- {
newK := k
if x > 0 {
newK--
}
f[j+1][k+1] = max(f[j+1][newK+1], f[j][newK+1]) + x
}
}
}
ans := f[n][K+1]
if ans < 0 {
return -1
}
return ans
}
从 $(0,0)$ 移动到 $(m-1,n-1)$，至多花费 $m+n-2$（注意题目保证 $\textit{grid}[0][0] = 0$）。所以可以把 $K$ 更新为 $\min(K, m+n-2)$。
此外，从 $(0,0)$ 移动到 $(i,j)$ 至多花费 $i+j$，所以最内层循环的 $k$ 最大是 $\min(K,i+j)$。
改成这种写法后，由于 $f$ 的定义是「至多」，$f[i][j][>i+j]$ 的状态本该更新，但没有更新。所以最后返回的是 $\max(f[m][n])$。
也可以把 $f$ 的定义改成「恰好」，这样只需要把 $f[0][1][1]$ 初始化成 $0$，其余均为 $-\infty$。
此外，可以加一个特判，如果从起点到终点的最小花费都大于 $K$，那么不存在有效路径，返回 $-1$。做法类似 64. 最小路径和，我的题解。
注：更精细的写法是，写一个额外的 DP，计算起点到每个位置的最大花费。
###py
# 手写 min max 更快
fmin = lambda a, b: b if b < a else a
fmax = lambda a, b: b if b > a else a
class Solution:
# 64. 最小路径和
def minPathSum(self, grid: List[List[int]]) -> int:
f = [inf] * (len(grid[0]) + 1)
f[1] = 0
for row in grid:
for j, x in enumerate(row):
f[j + 1] = fmin(f[j], f[j + 1]) + fmin(x, 1) # 值大于 0 的单元格花费 1
return f[-1]
def maxPathScore(self, grid: List[List[int]], K: int) -> int:
if self.minPathSum(grid) > K:
return -1
m, n = len(grid), len(grid[0])
K = fmin(K, m + n - 2) # 至多花费 m+n-2
f = [[-inf] * (K + 2) for _ in range(n + 1)]
f[1][1] = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
for k in range(fmin(K, i + j), -1, -1): # 从 (0,0) 到 (i,j) 至多花费 i+j
new_k = k - 1 if x else k
f[j + 1][k + 1] = fmax(f[j + 1][new_k + 1], f[j][new_k + 1]) + x
return max(f[n])
###java
class Solution {
public int maxPathScore(int[][] grid, int K) {
if (minPathSum(grid) > K) {
return -1;
}
int m = grid.length;
int n = grid[0].length;
K = Math.min(K, m + n - 2); // 至多花费 m+n-2
int[][] f = new int[n + 1][K + 2];
for (int[] row : f) {
Arrays.fill(row, Integer.MIN_VALUE);
}
f[1][1] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = grid[i][j];
for (int k = Math.min(K, i + j); k >= 0; k--) { // 从 (0,0) 到 (i,j) 至多花费 i+j
int newK = x > 0 ? k - 1 : k;
f[j + 1][k + 1] = Math.max(f[j + 1][newK + 1], f[j][newK + 1]) + x;
}
}
}
int ans = 0;
for (int x : f[n]) {
ans = Math.max(ans, x);
}
return ans;
}
// 64. 最小路径和
private int minPathSum(int[][] grid) {
int n = grid[0].length;
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MAX_VALUE);
f[1] = 0;
for (int[] row : grid) {
for (int j = 0; j < n; j++) {
f[j + 1] = Math.min(f[j], f[j + 1]) + Math.min(row[j], 1); // 值大于 0 的单元格花费 1
}
}
return f[n];
}
}
###cpp
class Solution {
// 64. 最小路径和
int minPathSum(vector<vector<int>>& grid) {
int n = grid[0].size();
vector<int> f(n + 1, INT_MAX);
f[1] = 0;
for (auto& row : grid) {
for (int j = 0; j < n; j++) {
f[j + 1] = min(f[j], f[j + 1]) + min(row[j], 1); // 值大于 0 的单元格花费 1
}
}
return f[n];
}
public:
int maxPathScore(vector<vector<int>>& grid, int K) {
if (minPathSum(grid) > K) {
return -1;
}
int m = grid.size(), n = grid[0].size();
K = min(K, m + n - 2); // 至多花费 m+n-2
vector f(n + 1, vector<int>(K + 2, INT_MIN));
f[1][1] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = grid[i][j];
for (int k = min(K, i + j); k >= 0; k--) { // 从 (0,0) 到 (i,j) 至多花费 i+j
int new_k = k - (x > 0);
f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x;
}
}
}
return ranges::max(f[n]);
}
};
###go
// 64. 最小路径和
func minPathSum(grid [][]int) int {
n := len(grid[0])
f := make([]int, n+1)
for j := range f {
f[j] = math.MaxInt
}
f[1] = 0
for _, row := range grid {
for j, x := range row {
f[j+1] = min(f[j], f[j+1]) + min(x, 1) // 值大于 0 的单元格花费 1
}
}
return f[n]
}
func maxPathScore(grid [][]int, K int) int {
if minPathSum(grid) > K {
return -1
}
m, n := len(grid), len(grid[0])
K = min(K, m+n-2) // 至多花费 m+n-2
f := make([][]int, n+1)
for j := range f {
f[j] = make([]int, K+2)
for k := range f[j] {
f[j][k] = math.MinInt
}
}
f[1][1] = 0
for i, row := range grid {
for j, x := range row {
for k := min(K, i+j); k >= 0; k-- { // 从 (0,0) 到 (i,j) 至多花费 i+j
newK := k
if x > 0 {
newK--
}
f[j+1][k+1] = max(f[j+1][newK+1], f[j][newK+1]) + x
}
}
}
return slices.Max(f[n])
}
见下面动态规划题单的「二、网格图 DP」。
给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。
如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。
请你返回执行任意次操作以后，最终网格图的 最大 总分数。
示例 1：
输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：11
解释：
第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。
示例 2：
输入：grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
输出：94
解释：
我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。
提示：
1 <= n == grid.length <= 100n == grid[i].length0 <= grid[i][j] <= 109