给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。
示例 1：
输入：mat = [[1,0,1],[1,1,0],[1,1,0]] 输出：13 解释： 有 6 个 1x1 的矩形。 有 2 个 1x2 的矩形。 有 3 个 2x1 的矩形。 有 1 个 2x2 的矩形。 有 1 个 3x1 的矩形。 矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
示例 2：
输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]] 输出：24 解释： 有 8 个 1x1 的子矩形。 有 5 个 1x2 的子矩形。 有 2 个 1x3 的子矩形。 有 4 个 2x1 的子矩形。 有 2 个 2x2 的子矩形。 有 2 个 3x1 的子矩形。 有 1 个 3x2 的子矩形。 矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
提示：
登录1 <= m, n <= 150mat[i][j] 仅包含 0 或 1
枚举子矩形的上下边界，统计每一列的 $1$ 的个数，把原问题「压缩」为一维数组上的问题。
在示例 2 中，假设现在枚举到子矩形的上边界为 $0$ 行，下边界为 $1$ 行，即 $\textit{mat}$ 的前两行。子矩形的高 $h=2$。
统计每一列的 $1$ 的个数，得到一个一维数组 $a=[0,2,2,1]$。我们要找的子矩形，就是 $a$ 的子数组。由于全 $1$ 子矩形的每一列都是 $1$，所以子数组的每一项都得是子矩形的高 $h=2$。问题变成：
做法同 2348. 全 0 子数组的数目。
代码实现时，外层循环枚举上边界，内层循环枚举下边界。当下边界 $\textit{bottom}$ 加一时，只需把每个 $a[j]$ 都增加相应的 $\textit{mat}[\textit{bottom}][j]$，无需整个重新统计。
###py
class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
ans = 0
for top in range(m): # 枚举上边界
a = [0] * n
for bottom in range(top, m): # 枚举下边界
h = bottom - top + 1 # 高
# 2348. 全 h 子数组的数目
last = -1
for j in range(n):
a[j] += mat[bottom][j] # 把 bottom 这一行的值加到 a 中
if a[j] != h:
last = j # 记录上一个非 h 元素的位置
else:
ans += j - last
return ans
###java
class Solution {
public int numSubmat(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int ans = 0;
for (int top = 0; top < m; top++) { // 枚举上边界
int[] a = new int[n];
for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
int h = bottom - top + 1; // 高
// 2348. 全 h 子数组的数目
int last = -1;
for (int j = 0; j < n; j++) {
a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
if (a[j] != h) {
last = j; // 记录上一个非 h 元素的位置
} else {
ans += j - last;
}
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int ans = 0;
for (int top = 0; top < m; top++) { // 枚举上边界
vector<int> a(n);
for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
int h = bottom - top + 1; // 高
// 2348. 全 h 子数组的数目
int last = -1;
for (int j = 0; j < n; j++) {
a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
if (a[j] != h) {
last = j; // 记录上一个非 h 元素的位置
} else {
ans += j - last;
}
}
}
}
return ans;
}
};
###go
func numSubmat(mat [][]int) (ans int) {
m, n := len(mat), len(mat[0])
for top := range m { // 枚举上边界
a := make([]int, n)
for bottom := top; bottom < m; bottom++ { // 枚举下边界
h := bottom - top + 1 // 高
// 2348. 全 h 子数组的数目
last := -1
for j := range n {
a[j] += mat[bottom][j] // 把 bottom 这一行的值加到 a 中
if a[j] != h {
last = j // 记录上一个非 h 元素的位置
} else {
ans += j - last
}
}
}
}
return
}
枚举子矩形的右下角（枚举底边，枚举右边界），有多少个对应的子矩形？
举个例子。
在示例 2 中，当我们枚举到最后一行时，柱子高度为 $\textit{heights}=[1,3,3,0]$。然后枚举子矩形的右边界：
一般地，用 单调栈 计算小于 $\textit{heights}[j]$ 的左边最近柱子的位置 $\textit{left}$，把子矩形分成两类：
###py
class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
heights = [0] * len(mat[0])
ans = 0
for row in mat:
for j, x in enumerate(row):
if x == 0:
heights[j] = 0
else:
heights[j] += 1
# (j, f, heights[j])
st = [(-1, 0, -1)] # 哨兵，方便处理 left=-1 的情况
for j, h in enumerate(heights):
while st[-1][2] >= h:
st.pop()
left, f, _ = st[-1]
# 计算底边为 row，右边界为 j 的子矩形个数
# 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
# 左边界 > left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
f += (j - left) * h
ans += f
st.append((j, f, h))
return ans
###java
class Solution {
public int numSubmat(int[][] mat) {
int n = mat[0].length;
int[] heights = new int[n];
int ans = 0;
int[][] st = new int[n + 1][3]; // (j, f, heights[j])
for (int[] row : mat) {
for (int j = 0; j < n; j++) {
if (row[j] == 0) {
heights[j] = 0;
} else {
heights[j]++;
}
}
st[0][0] = st[0][2] = -1; // 哨兵，方便处理 left=-1 的情况
int top = 0;
for (int j = 0; j < n; j++) {
int h = heights[j];
while (st[top][2] >= h) {
top--; // 出栈
}
int left = st[top][0];
int f = st[top][1];
// 计算底边为 row，右边界为 j 的子矩形个数
// 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
// 左边界 > left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
f += (j - left) * h;
ans += f;
top++;
st[top][0] = j; // 入栈
st[top][1] = f;
st[top][2] = h;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n = mat[0].size();
vector<int> heights(n);
int ans = 0;
for (auto& row : mat) {
for (int j = 0; j < n; j++) {
if (row[j] == 0) {
heights[j] = 0;
} else {
heights[j]++;
}
}
stack<tuple<int, int, int>> st; // (j, f, heights[j])
st.emplace(-1, 0, -1); // 哨兵，方便处理 left=-1 的情况
for (int j = 0; j < n; j++) {
int h = heights[j];
while (get<2>(st.top()) >= h) {
st.pop();
}
auto [left, f, _] = st.top();
// 计算底边为 row，右边界为 j 的子矩形个数
// 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
// 左边界 > left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
f += (j - left) * h;
ans += f;
st.emplace(j, f, h);
}
}
return ans;
}
};
###go
func numSubmat(mat [][]int) (ans int) {
heights := make([]int, len(mat[0]))
for _, row := range mat {
for j, x := range row {
if x == 0 {
heights[j] = 0
} else {
heights[j]++
}
}
type tuple struct{ j, f, h int }
st := []tuple{{-1, 0, -1}} // 哨兵，方便处理 left=-1 的情况
for j, h := range heights {
for st[len(st)-1].h >= h {
st = st[:len(st)-1]
}
p := st[len(st)-1]
left, f := p.j, p.f
// 计算底边为 row，右边界为 j 的子矩形个数
// 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
// 左边界 > left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
f += (j - left) * h
ans += f
st = append(st, tuple{j, f, h})
}
}
return
}
见下面单调栈题单的「二、矩形」。
欢迎关注 B站@灵茶山艾府
看了很多题解，大家大致的思路基本一致，时间复杂度为O(n·n·m)，但大多题解没有把过程表述的很完整，作为一个刷题的小白，我想在这写写小白也能看懂的思路，和做这道题的一些细节和收获
题目要求既要考虑1x2, 2x1的情况, 也要考虑2x2的情况：
(1)先考虑1xn的情况，即在一行中(横向)可以找出多少个矩形**(这步我称之为"统计")**，代码如下：统计行中的矩形数目 int now = 0; for (int k = 0; k < col; k++){ if (mat[j][k] == 0) now = 0; else now = k == 0 ? mat[j][0] : now + 1; ans += now; }
(2)压缩：
起始的二维数组
对其使用“按位与”进行压缩
第二次统计的结果
思考：这里我们可以发现第二次的统计是2xn的，既包含了2X1的情况也包含了2x2的情况，接下来的步骤继续如上循环"压缩"即可
###java
class Solution {
public int numSubmat(int[][] mat) {
int row = mat.length, col = mat[0].length, ans = 0;
for (int i = 0; i < row; i++){
//统计
for (int j = i; j < row; j++){
int now = 0;
for (int k = 0; k < col; k++){
if (mat[j][k] == 0) now = 0;
else now = k == 0 ? mat[j][0] : now + 1;
ans += now;
}
}
//压缩
for (int j = row - 1; j > i; j--){
for (int k = 0; k < col; k++){
mat[j][k] = mat[j][k] & mat[j - 1][k];
}
}
}
return ans;
}
}
希望这篇题解能让你看懂，喜欢的留下你宝贵的会心一赞吧，刷题之路，我们绝不言败！ヾ(◍°∇°◍)ﾉﾞ
矩阵里每个点(i.j)统计他这行左边到他这个位置最多有几个连续的1，存为left[i][j]。然后对于每个点(i.j)，我们固定子矩形的右下角为(i.j)，利用left从该行i向上寻找子矩阵左上角为第k行的矩阵个数。每次将子矩阵个数加到答案中即可。
时间复杂度O(nnm)，空间复杂度O(nm)。
###cpp
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
vector<vector<int> > left(n,vector<int>(m));
int now = 0;
for(int i=0;i<n;i++){
now = 0;
for(int j=0;j<m;j++){
if(mat[i][j] == 1) now ++;
else now = 0;
left[i][j] = now;
}
}
int ans = 0,minx;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
minx = 0x3f3f3f3f;
for(int k=i;k>=0;k--){
minx = min(left[k][j],minx);
ans += minx;
}
}
}
return ans;
}
};
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 输出：7 解释： 边长为 1 的正方形有 6 个。 边长为 2 的正方形有 1 个。 正方形的总数 = 6 + 1 = 7.
提示：
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1思路启发：学习 二维前缀和 对于想出本题的转移方程有帮助。
整理上图中的结论。定义 $f_{i,j}$ 为右下角在 $(i,j)$ 的全 $1$ 正方形的最大边长。我们有
$$
f_{i,j} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i-1,j-1},f_{i-1,j},f_{i,j-1}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$
然而，当 $i=0$ 或者 $j=0$ 时，上式会产生负数下标 $-1$。
为避免出现负数下标，可以在 $f$ 矩阵的最上边添加一行 $0$，最左边添加一列 $0$，对应下标出界的状态（正方形的最大边长为 $0$）。
由于修改了 $f$，状态转移方程中的 $f$ 的下标要加一，即
$$
f_{i+1,j+1} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i,j},f_{i,j+1},f_{i+1,j}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$
注意 $\textit{matrix}$ 的下标是不用变的，因为我们只是在 $f$ 矩阵的上边和左边插入了 $0$，所以只有 $f$ 的下标受此影响需要加一。
初始值 $f_{0,j} = f_{i,0} = 0$。
根据图中的结论（个数等于最大边长），答案为整个 $f$ 矩阵的元素和。
###py
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
f = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(matrix):
for j, x in enumerate(row):
if x:
f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1
return sum(map(sum, f))
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] f = new int[m + 1][n + 1];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] > 0) {
f[i + 1][j + 1] = Math.min(Math.min(f[i][j], f[i][j + 1]), f[i + 1][j]) + 1;
ans += f[i + 1][j + 1];
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector f(m + 1, vector<int>(n + 1));
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j]) {
f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1;
ans += f[i + 1][j + 1];
}
}
}
return ans;
}
};
###go
func countSquares(matrix [][]int) (ans int) {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i, row := range matrix {
for j, x := range row {
if x > 0 {
f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1
ans += f[i+1][j+1]
}
}
}
return
}
直接把 $\textit{matrix}$ 当作 $f$，原地修改。
###py
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
for i, row in enumerate(matrix):
for j, x in enumerate(row):
if x and i and j:
row[j] += min(matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1])
return sum(map(sum, matrix))
###java
class Solution {
public int countSquares(int[][] matrix) {
int ans = 0;
for (int i = 0; i < matrix.length; i++) {
int[] row = matrix[i];
for (int j = 0; j < row.length; j++) {
if (row[j] > 0 && i > 0 && j > 0) {
row[j] += Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), row[j - 1]);
}
ans += row[j];
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
for (int i = 0; i < matrix.size(); i++) {
auto& row = matrix[i];
for (int j = 0; j < row.size(); j++) {
if (i && j && row[j]) {
row[j] += min({matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]});
}
ans += row[j];
}
}
return ans;
}
};
###go
func countSquares(matrix [][]int) (ans int) {
for i, row := range matrix {
for j, x := range row {
if x > 0 && i > 0 && j > 0 {
row[j] += min(matrix[i-1][j], matrix[i-1][j-1], row[j-1])
}
ans += row[j]
}
}
return
}
见下面动态规划题单的「§7.5 子矩形 DP」。
欢迎关注 B站@灵茶山艾府
思路
我们用 $f[i][j]$ 表示以 $(i, j)$ 为右下角的正方形的最大边长，那么除此定义之外，$f[i][j] = x$ 也表示以 $(i, j)$ 为右下角的正方形的数目为 $x$（即边长为 $1, 2, \cdots, x$ 的正方形各一个）。在计算出所有的 $f[i][j]$ 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。
我们尝试挖掘 $f[i][j]$ 与相邻位置的关系来计算出 $f[i][j]$ 的值。
如上图所示，若对于位置 $(i, j)$ 有 $f[i][j] = 4$，我们将以 $(i, j)$ 为右下角、边长为 $4$ 的正方形涂上色，可以发现其左侧位置 $(i, j - 1)$，上方位置 $(i - 1, j)$ 和左上位置 $(i - 1, j - 1)$ 均可以作为一个边长为 $4 - 1 = 3$ 的正方形的右下角。也就是说，这些位置的的 $f$ 值至少为 $3$，即：
将这三个不等式联立，可以得到：
$$\texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])\ge f[i][j]−1$$
这是我们通过固定 $f[i][j]$ 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 $f[i][j]$ 相邻位置的值，得到另外的限制条件。
如上图所示，假设 $f[i][j - 1]$，$f[i - 1][j]$ 和 $f[i - 1][j - 1]$ 中的最小值为 $3$，即，$(i, j - 1)$，$(i - 1, j)$ 和 $(i - 1, j - 1)$ 均可以作为一个边长为 $3$ 的正方形的右下角。我们将这些边长为 $3$ 的正方形依次涂上色，可以发现，如果位置 $(i, j)$ 的元素为 $1$，那么它可以作为一个边长为 $4$ 的正方形的右下角，$f$ 值至少为 $4$，即：
$$f[i][j]\geq \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$
将其与上一个不等式联立，可以得到：
$$f[i][j] = \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$
再考虑一些边界情况，我们就得到了完整的递推式：
$$
f[i][j] =
\begin{cases}
matrix[i][j] & \texttt{if } i=0 \texttt{ or } j=0 \
0 & \texttt{if } matrix[i][j]=0 \
\min(f[i][j-1], f[i-1][j], f[i-1][j-1]) + 1 & \texttt{otherwise}
\end{cases}
$$
我们按照行优先的顺序依次计算 $f[i][j]$ 的值，累加就可以得到最终的答案。
代码
###Python
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
f = [[0] * n for _ in range(m)]
ans = 0
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
f[i][j] = matrix[i][j]
elif matrix[i][j] == 0:
f[i][j] = 0
else:
f[i][j] = min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1
ans += f[i][j]
return ans
###C++
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> f(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = min({f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]}) + 1;
}
ans += f[i][j];
}
}
return ans;
}
};
###Java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] f = new int[m][n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(Math.min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
}
}
###C#
public class Solution {
public int CountSquares(int[][] matrix) {
int m = matrix.Length, n = matrix[0].Length;
int[,] f = new int[m, n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i, j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i, j] = 0;
} else {
f[i, j] = Math.Min(Math.Min(f[i, j - 1], f[i - 1, j]), f[i - 1, j - 1]) + 1;
}
ans += f[i, j];
}
}
return ans;
}
}
###Go
func countSquares(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 || j == 0 {
f[i][j] = matrix[i][j]
} else if matrix[i][j] == 0 {
f[i][j] = 0
} else {
f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1
}
ans += f[i][j]
}
}
return ans
}
###C
int countSquares(int** matrix, int matrixSize, int* matrixColSize) {
int m = matrixSize, n = matrixColSize[0];
int** f = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; ++i) {
f[i] = (int*)malloc(n * sizeof(int));
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = fmin(f[i][j - 1], fmin(f[i - 1][j], f[i - 1][j - 1])) + 1;
}
ans += f[i][j];
}
}
for (int i = 0; i < m; ++i) {
free(f[i]);
}
free(f);
return ans;
}
###JavaScript
var countSquares = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i === 0 || j === 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] === 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
};
###TypeScript
function countSquares(matrix: number[][]): number {
const m = matrix.length, n = matrix[0].length;
const f: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i === 0 || j === 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] === 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
}
###Rust
impl Solution {
pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
let m = matrix.len();
let n = matrix[0].len();
let mut f = vec![vec![0; n]; m];
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if i == 0 || j == 0 {
f[i][j] = matrix[i][j];
} else if matrix[i][j] == 0 {
f[i][j] = 0;
} else {
f[i][j] = f[i][j - 1].min(f[i - 1][j]).min(f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
ans
}
}
复杂度分析
时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 是输入 $\textit{matrix}$ 的行和列。
空间复杂度：$O(m\times n)$。
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：
matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出： 15
解释：
边长为1的正方形有10个。
边长为2的正方形有4个。
边长为3的正方形有1个。
正方形的总数 =10+4+1=15.
示例 2：
输入：
matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出： 7
解释：
边长为1的正方形有6个。
边长为2的正方形有1个。
正方形的总数 =6+1=7.
首先，暴力解就是以矩阵每一个点为起点，依次判断边长为1，2，3，...，min{m, n}的区域是否是全1正方形(该区域所有点的和等于该区域面积)，显然，这种复杂度是过不了的。
很容易知道，上述过程在判断较大区域是否为正方形的时候，并没有用到前面计算的结果，每一次判断都从头开始。这也是复杂度过高的原因。
那么怎么利用之前判断过的结果呢？举个例子，比如我要判断以(2, 3)为右下角边长为3的正方形区域（红色边框区域）是否是全为1：
(i, j)位置是否为1，如果否，则显然不满足；如果是，进行下一步判断(i - 1, j), (i - 1, j - 1), (i, j - 1)为右下角的区域是否能构成边长为2的正方形，如果能，那就满足条件。
基于上述，我们可以看出思路大致跟最大正方形那题差不多，设dp[i][j][k]表示以(i, j)为右下角，边长为k的正方形区域是否全为1，那么易得出如下状态转移方程：
###java
dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int len = Math.min(m, n);
boolean[][][] dp = new boolean[m][n][len];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][0] = (matrix[i][j] == 1);
count += dp[i][j][0] ? 1 : 0;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
for (int k = 1; k < len; k++) {
dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);
if (dp[i][j][k]) {
count++;
}
}
}
}
return count;
}
}
经评论区@da-fei-kai提醒，上述代码可以做进一步优化。
首先，题目并不关心边长为
1,2,...,k的各有多少个，并且我们知道，以(i, j)为右下角边长为k的正方形全为1的话，那么以(i, j)为右下角边长分别为1,2,...,k - 1的正方形区域一定是全为1，如下图：
上图中，如果红色区域是边长为
3的全1正方形区域，那么它一定包含了一个边长为2和边长为1的全1正方形区域。所以，我们只需记录以(i, j)为右下角的区域包含的最大全1正方形边长即可，这个最大边长也即以(i , j)为右下角的全1正方形的个数.
那么基于此，我们就可以将原始的dp降一维度，设dp[i][j]表示以(i, j)为右下角的最大全1正方形区域的边长，则有如下状态转移方程：
###java
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
这就和最大正方形那题的状态转移方程完全一样了。
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int ans = 0;
// 预处理每一行和每一列
for (int i = 0; i < m; i++) {
ans += dp[i][0] = matrix[i][0];
}
for (int j = 0; j < n; j++) {
ans += dp[0][j] = matrix[0][j];
}
// 上述过程(0, 0)判断了两次, 如果matrix[0][0] == 1，说明ans多算了一个
if (matrix[0][0] == 1) {
ans--;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
ans += dp[i][j];
}
}
}
return ans;
}
}
给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。
子数组 是一个数组中一段连续非空元素组成的序列。
示例 1：
输入：nums = [1,3,0,0,2,0,0,4] 输出：6 解释： 子数组 [0] 出现了 4 次。 子数组 [0,0] 出现了 2 次。 不存在长度大于 2 的全 0 子数组，所以我们返回 6 。
示例 2：
输入：nums = [0,0,0,2,0,0] 输出：9 解释： 子数组 [0] 出现了 5 次。 子数组 [0,0] 出现了 3 次。 子数组 [0,0,0] 出现了 1 次。 不存在长度大于 3 的全 0 子数组，所以我们返回 9 。
示例 3：
输入：nums = [2,10,2019] 输出：0 解释：没有全 0 子数组，所以我们返回 0 。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109本题做法很多，下面讲两个更具一般性的方法。
子数组越长，越可能包含非零元素，不满足题目要求；子数组越短，越可能全为 $0$，满足题目要求。我们枚举子数组的右端点，当右端点变大（子数组变长）的时候，子数组左端点要么不变，要么也变大。
不仅是本题，有这样性质的题目，都可以用滑动窗口解决，见 滑动窗口【基础算法精讲 03】。
本题属于「越短越合法」型滑动窗口。由于题目的特殊性，有更简单的解决方法：
示例 1 的 $\textit{nums} = [1,3,0,0,2,0,0,4]$，当右端点在 $i=3$ 时，$\textit{last}=1$，我们找到了 $i-\textit{last}=2$ 个右端点在 $3$ 的全 $0$ 子数组，加入答案。
为了兼容 $\textit{nums}=[0,0,0,2,0,0]$ 这种一开始就是 $0$ 的情况，初始化 $\textit{last}=-1$。
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
ans = 0
last = -1
for i, x in enumerate(nums):
if x:
last = i # 记录上一个非 0 元素的位置
else:
ans += i - last
return ans
class Solution {
public long zeroFilledSubarray(int[] nums) {
long ans = 0;
int last = -1;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (x != 0) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
}
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long ans = 0;
int last = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i]) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
};
long long zeroFilledSubarray(int* nums, int numsSize) {
long long ans = 0;
int last = -1;
for (int i = 0; i < numsSize; i++) {
if (nums[i]) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
func zeroFilledSubarray(nums []int) (ans int64) {
last := -1
for i, x := range nums {
if x != 0 {
last = i // 记录上一个非 0 元素的位置
} else {
ans += int64(i - last)
}
}
return
}
var zeroFilledSubarray = function(nums) {
let ans = 0;
let last = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
};
impl Solution {
pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
let mut ans = 0;
let mut last = -1;
for (i, x) in nums.into_iter().enumerate() {
let i = i as i64;
if x != 0 {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += (i - last) as i64;
}
}
ans
}
}
遍历到 $\textit{nums}[i]=0$，现在来计算右端点为 $i$ 的全 $0$ 子数组的个数。
我们可以在右端点为 $i-1$ 的全 $0$ 子数组的末尾添加一个 $0$。比如右端点为 $i-1$ 的全 $0$ 子数组有 $5$ 个，那么在这 $5$ 个子数组的末尾添加 $\textit{nums}[i]=0$，再算上 $\textit{nums}[i]$ 单独组成一个长为 $1$ 的子数组，我们得到了 $5+1=6$ 个右端点为 $i$ 的全 $0$ 子数组，加入答案。
具体来说：
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
ans = cnt0 = 0
for x in nums:
if x:
cnt0 = 0
else:
cnt0 += 1 # 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0
return ans
class Solution {
public long zeroFilledSubarray(int[] nums) {
long ans = 0;
int cnt0 = 0;
for (int x : nums) {
if (x != 0) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
}
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long ans = 0;
int cnt0 = 0;
for (int x : nums) {
if (x) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
};
long long zeroFilledSubarray(int* nums, int numsSize) {
long long ans = 0;
int cnt0 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i]) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
func zeroFilledSubarray(nums []int) (ans int64) {
cnt0 := 0
for _, x := range nums {
if x != 0 {
cnt0 = 0
} else {
cnt0++ // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += int64(cnt0)
}
}
return
}
var zeroFilledSubarray = function(nums) {
let ans = 0;
let cnt0 = 0;
for (const x of nums) {
if (x !== 0) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
};
impl Solution {
pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
let mut ans = 0;
let mut cnt0 = 0;
for x in nums {
if x != 0 {
cnt0 = 0;
} else {
cnt0 += 1; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0 as i64;
}
}
ans
}
}
注：本题还有其他方法，例如找极大连续 $0$ 的长度，然后用等差数列计算。
方法一：滑动窗口题单的「§2.3.1 越短越合法」。
方法二：动态规划题单「§7.3 子数组 DP」的「思维扩展」。
欢迎关注 B站@灵茶山艾府
###python3
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
groups = [(char, len(list(group))) for char, group in groupby(nums)]
return sum(count * (count + 1) // 2 for char, count in groups if char == 0)
统计连续0出现的次数，即为构成当前子数组的数量：
一个0，构成数组：
[0] //第一个0
两个0，构成数组：
[0] //第一个0
[0,0] //第一个0和第二个0
[0] //第二个0
三个0，构成数组：
三个0包含两个0的所有情况：
[0] //第一个0
[0,0] //第一个0和第二个0
[0] //第二个0
两个0的所有情况+第三个0
[0] //第一个0 和第三个0（以[0]单独构成子数组）
[0,0,0] //第一个0和第二个0 和第三个0
[0,0] //第二个0 和第三个0
状态转移方程：
连续的n个0对答案的贡献 = 连续的n-1个0对答案的贡献 + n
###java
class Solution {
public long zeroFilledSubarray(int[] nums) {
long count = 0;//答案
int zeroCnt = 0;//当前0的个数
for (int x : nums) {
if (x == 0) {
zeroCnt++;
count += zeroCnt;
} else {
zeroCnt = 0;
}
}
return count;
}
}
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。
你须遵守以下规则:
'/' 表示实数除法，而不是整数除法。
4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。“-” 作为一元运算符。
cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。
示例 1:
输入: cards = [4, 1, 8, 7] 输出: true 解释: (8-4) * (7-1) = 24
示例 2:
输入: cards = [1, 2, 1, 2] 输出: false
提示:
cards.length == 41 <= cards[i] <= 9微软一面平行面出了这个题, 比这个还麻烦, 给的输入是 n 个数字
用的 Java 回溯解决的, 第一轮已经通过
提一下需要注意的细节
###Java
class Solution {
private static final double TARGET = 24;
private static final double EPISLON = 1e-6;
public boolean judgePoint24(int[] cards) {
return helper(new double[]{ cards[0], cards[1], cards[2], cards[3] });
}
private boolean helper(double[] nums) {
if (nums.length == 1) return Math.abs(nums[0] - TARGET) < EPISLON;
// 每次选择两个不同的数进行回溯
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// 将选择出来的两个数的计算结果和原数组剩下的数加入 next 数组
double[] next = new double[nums.length - 1];
for (int k = 0, pos = 0; k < nums.length; k++) if (k != i && k != j) next[pos++] = nums[k];
for (double num : calculate(nums[i], nums[j])) {
next[next.length - 1] = num;
if (helper(next)) return true;
}
}
}
return false;
}
private List<Double> calculate(double a, double b) {
List<Double> list = new ArrayList<>();
list.add(a + b);
list.add(a - b);
list.add(b - a);
list.add(a * b);
if (!(Math.abs(b) < EPISLON)) list.add(a / b);
if (!(Math.abs(a) < EPISLON)) list.add(b / a);
return list;
}
}
Python一行大法好!
###Python
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
return sorted(nums) in [[1, 1, 1, 8], [1, 1, 2, 6], [1, 1, 2, 7], [1, 1, 2, 8], [1, 1, 2, 9], [1, 1, 3, 4], [1, 1, 3, 5], [1, 1, 3, 6], [1, 1, 3, 7], [1, 1, 3, 8], [1, 1, 3, 9], [1, 1, 4, 4], [1, 1, 4, 5], [1, 1, 4, 6], [1, 1, 4, 7], [1, 1, 4, 8], [1, 1, 4, 9], [1, 1, 5, 5], [1, 1, 5, 6], [1, 1, 5, 7], [1, 1, 5, 8], [1, 1, 6, 6], [1, 1, 6, 8], [1, 1, 6, 9], [1, 1, 8, 8], [1, 2, 2, 4], [1, 2, 2, 5], [1, 2, 2, 6], [1, 2, 2, 7], [1, 2, 2, 8], [1, 2, 2, 9], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], [1, 2, 3, 9], [1, 2, 4, 4], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4, 7], [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5, 5], [1, 2, 5, 6], [1, 2, 5, 7], [1, 2, 5, 8], [1, 2, 5, 9], [1, 2, 6, 6], [1, 2, 6, 7], [1, 2, 6, 8], [1, 2, 6, 9], [1, 2, 7, 7], [1, 2, 7, 8], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 8, 9], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 3, 5], [1, 3, 3, 6], [1, 3, 3, 7], [1, 3, 3, 8], [1, 3, 3, 9], [1, 3, 4, 4], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4, 7], [1, 3, 4, 8], [1, 3, 4, 9], [1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 6], [1, 3, 6, 7], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 7], [1, 3, 7, 8], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 8, 9], [1, 3, 9, 9], [1, 4, 4, 4], [1, 4, 4, 5], [1, 4, 4, 6], [1, 4, 4, 7], [1, 4, 4, 8], [1, 4, 4, 9], [1, 4, 5, 5], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 6], [1, 4, 6, 7], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 7], [1, 4, 7, 8], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 8, 9], [1, 5, 5, 5], [1, 5, 5, 6], [1, 5, 5, 9], [1, 5, 6, 6], [1, 5, 6, 7], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [1, 5, 8, 8], [1, 5, 8, 9], [1, 5, 9, 9], [1, 6, 6, 6], [1, 6, 6, 8], [1, 6, 6, 9], [1, 6, 7, 9], [1, 6, 8, 8], [1, 6, 8, 9], [1, 6, 9, 9], [1, 7, 7, 9], [1, 7, 8, 8], [1, 7, 8, 9], [1, 7, 9, 9], [1, 8, 8, 8], [1, 8, 8, 9], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 8], [2, 2, 2, 9], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 3, 5], [2, 2, 3, 6], [2, 2, 3, 7], [2, 2, 3, 8], [2, 2, 3, 9], [2, 2, 4, 4], [2, 2, 4, 5], [2, 2, 4, 6], [2, 2, 4, 7], [2, 2, 4, 8], [2, 2, 4, 9], [2, 2, 5, 5], [2, 2, 5, 6], [2, 2, 5, 7], [2, 2, 5, 8], [2, 2, 5, 9], [2, 2, 6, 6], [2, 2, 6, 7], [2, 2, 6, 8], [2, 2, 6, 9], [2, 2, 7, 7], [2, 2, 7, 8], [2, 2, 8, 8], [2, 2, 8, 9], [2, 3, 3, 3], [2, 3, 3, 5], [2, 3, 3, 6], [2, 3, 3, 7], [2, 3, 3, 8], [2, 3, 3, 9], [2, 3, 4, 4], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4, 7], [2, 3, 4, 8], [2, 3, 4, 9], [2, 3, 5, 5], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 6], [2, 3, 6, 7], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 7], [2, 3, 7, 8], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 8, 9], [2, 3, 9, 9], [2, 4, 4, 4], [2, 4, 4, 5], [2, 4, 4, 6], [2, 4, 4, 7], [2, 4, 4, 8], [2, 4, 4, 9], [2, 4, 5, 5], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 6], [2, 4, 6, 7], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 7], [2, 4, 7, 8], [2, 4, 7, 9], [2, 4, 8, 8], [2, 4, 8, 9], [2, 4, 9, 9], [2, 5, 5, 7], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 6], [2, 5, 6, 7], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 7], [2, 5, 7, 8], [2, 5, 7, 9], [2, 5, 8, 8], [2, 5, 8, 9], [2, 6, 6, 6], [2, 6, 6, 7], [2, 6, 6, 8], [2, 6, 6, 9], [2, 6, 7, 8], [2, 6, 7, 9], [2, 6, 8, 8], [2, 6, 8, 9], [2, 6, 9, 9], [2, 7, 7, 8], [2, 7, 8, 8], [2, 7, 8, 9], [2, 8, 8, 8], [2, 8, 8, 9], [2, 8, 9, 9], [3, 3, 3, 3], [3, 3, 3, 4], [3, 3, 3, 5], [3, 3, 3, 6], [3, 3, 3, 7], [3, 3, 3, 8], [3, 3, 3, 9], [3, 3, 4, 4], [3, 3, 4, 5], [3, 3, 4, 6], [3, 3, 4, 7], [3, 3, 4, 8], [3, 3, 4, 9], [3, 3, 5, 5], [3, 3, 5, 6], [3, 3, 5, 7], [3, 3, 5, 9], [3, 3, 6, 6], [3, 3, 6, 7], [3, 3, 6, 8], [3, 3, 6, 9], [3, 3, 7, 7], [3, 3, 7, 8], [3, 3, 7, 9], [3, 3, 8, 8], [3, 3, 8, 9], [3, 3, 9, 9], [3, 4, 4, 4], [3, 4, 4, 5], [3, 4, 4, 6], [3, 4, 4, 7], [3, 4, 4, 8], [3, 4, 4, 9], [3, 4, 5, 5], [3, 4, 5, 6], [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 5, 9], [3, 4, 6, 6], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 7], [3, 4, 7, 8], [3, 4, 7, 9], [3, 4, 8, 9], [3, 4, 9, 9], [3, 5, 5, 6], [3, 5, 5, 7], [3, 5, 5, 8], [3, 5, 5, 9], [3, 5, 6, 6], [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9], [3, 5, 8, 8], [3, 5, 8, 9], [3, 5, 9, 9], [3, 6, 6, 6], [3, 6, 6, 7], [3, 6, 6, 8], [3, 6, 6, 9], [3, 6, 7, 7], [3, 6, 7, 8], [3, 6, 7, 9], [3, 6, 8, 8], [3, 6, 8, 9], [3, 6, 9, 9], [3, 7, 7, 7], [3, 7, 7, 8], [3, 7, 7, 9], [3, 7, 8, 8], [3, 7, 8, 9], [3, 7, 9, 9], [3, 8, 8, 8], [3, 8, 8, 9], [3, 8, 9, 9], [3, 9, 9, 9], [4, 4, 4, 4], [4, 4, 4, 5], [4, 4, 4, 6], [4, 4, 4, 7], [4, 4, 4, 8], [4, 4, 4, 9], [4, 4, 5, 5], [4, 4, 5, 6], [4, 4, 5, 7], [4, 4, 5, 8], [4, 4, 6, 8], [4, 4, 6, 9], [4, 4, 7, 7], [4, 4, 7, 8], [4, 4, 7, 9], [4, 4, 8, 8], [4, 4, 8, 9], [4, 5, 5, 5], [4, 5, 5, 6], [4, 5, 5, 7], [4, 5, 5, 8], [4, 5, 5, 9], [4, 5, 6, 6], [4, 5, 6, 7], [4, 5, 6, 8], [4, 5, 6, 9], [4, 5, 7, 7], [4, 5, 7, 8], [4, 5, 7, 9], [4, 5, 8, 8], [4, 5, 8, 9], [4, 5, 9, 9], [4, 6, 6, 6], [4, 6, 6, 7], [4, 6, 6, 8], [4, 6, 6, 9], [4, 6, 7, 7], [4, 6, 7, 8], [4, 6, 7, 9], [4, 6, 8, 8], [4, 6, 8, 9], [4, 6, 9, 9], [4, 7, 7, 7], [4, 7, 7, 8], [4, 7, 8, 8], [4, 7, 8, 9], [4, 7, 9, 9], [4, 8, 8, 8], [4, 8, 8, 9], [4, 8, 9, 9], [5, 5, 5, 5], [5, 5, 5, 6], [5, 5, 5, 9], [5, 5, 6, 6], [5, 5, 6, 7], [5, 5, 6, 8], [5, 5, 7, 7], [5, 5, 7, 8], [5, 5, 8, 8], [5, 5, 8, 9], [5, 5, 9, 9], [5, 6, 6, 6], [5, 6, 6, 7], [5, 6, 6, 8], [5, 6, 6, 9], [5, 6, 7, 7], [5, 6, 7, 8], [5, 6, 7, 9], [5, 6, 8, 8], [5, 6, 8, 9], [5, 6, 9, 9], [5, 7, 7, 9], [5, 7, 8, 8], [5, 7, 8, 9], [5, 8, 8, 8], [5, 8, 8, 9], [6, 6, 6, 6], [6, 6, 6, 8], [6, 6, 6, 9], [6, 6, 7, 9], [6, 6, 8, 8], [6, 6, 8, 9], [6, 7, 8, 9], [6, 7, 9, 9], [6, 8, 8, 8], [6, 8, 8, 9], [6, 8, 9, 9], [7, 8, 8, 9]]
游戏的第一步是挑出两个数，算出一个新数替代这两个数。
然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。
然后，在两个数中玩 24 点……
很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：
即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。
当递归返回 true，代表游戏成功，不用继续探索了，剩下的搜索分支全部砍掉。怎么做到？
isValid初始为 false，默认会执行||后面的递归。isValid就变为真，由于||的短路特性，后面的递归不会执行。isValid就像一个开关，避免写很多判断语句。###js
isValid = isValid || judgePoint24([...newNums, n1 + n2]);
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
// ...
const judgePoint24 = (nums) => {
const len = nums.length;
if (len == 1) { // 递归的出口
return Math.abs(nums[0] - 24) < 1e-9;
}
let isValid = false; // 用于控制是否进入递归
for (let i = 0; i < len; i++) { // 两层循环，枚举出所有的两数组合
for (let j = i + 1; j < len; j++) {
const n1 = nums[i];
const n2 = nums[j]; // 选出的两个数 n1 n2
const newNums = []; // 存放剩下的两个数
for (let k = 0; k < len; k++) {
if (k != i && k != j) { // 剔除掉选出的两个数
newNums.push(nums[k]);
}
}
// 加
isValid = isValid || judgePoint24([...newNums, n1 + n2]);
// 减与被减
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
// 乘
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
if (n2 !== 0) { // 除
isValid = isValid || judgePoint24([...newNums, n1 / n2]);
}
if (n1 !== 0) { // 被除
isValid = isValid || judgePoint24([...newNums, n2 / n1]);
}
if (isValid) {
return true;
}
}
}
return false; // 遍历结束，始终没有返回真，则返回false
};
func judgePoint24(nums []int) bool {
floatNums := make([]float64, len(nums))
for i := range floatNums {
floatNums[i] = float64(nums[i])
}
return dfs(floatNums)
}
func dfs(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-9
}
flag := false
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
n1, n2 := nums[i], nums[j]
newNums := make([]float64, 0, len(nums))
for k := 0; k < len(nums); k++ {
if k != i && k != j {
newNums = append(newNums, nums[k])
}
}
flag = flag || dfs(append(newNums, n1+n2))
flag = flag || dfs(append(newNums, n1-n2))
flag = flag || dfs(append(newNums, n2-n1))
flag = flag || dfs(append(newNums, n1*n2))
if n1 != 0 {
flag = flag || dfs(append(newNums, n2/n1))
}
if n2 != 0 {
flag = flag || dfs(append(newNums, n1/n2))
}
if flag {
return true
}
}
}
return false
}
Runtime: 68 ms, faster than 100.00% of JavaScript online submissions for 24 Game.
Runtime: 0 ms, faster than 100.00% of Go online submissions for 24 Game.
最后修改于：2022-01-10
一共有 $4$ 个数和 $3$ 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 $4$ 个数字中有序地选出 $2$ 个数字，共有 $4 \times 3=12$ 种选法，并选择加、减、乘、除 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $3$ 个数字。
然后在剩下的 $3$ 个数字中有序地选出 $2$ 个数字，共有 $3 \times 2=6$ 种选法，并选择 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $2$ 个数字。
最后剩下 $2$ 个数字，有 $2$ 种不同的顺序，并选择 $4$ 种运算操作之一。
因此，一共有 $12 \times 4 \times 6 \times 4 \times 2 \times 4=9216$ 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 $2$ 个数字，再选择一种运算操作，用计算得到的结果取代选出的 $2$ 个数字，这样列表中的数字就减少了 $1$ 个。重复上述步骤，直到列表中只剩下 $1$ 个数字，这个数字就是一种可能性的结果，如果结果等于 $24$，则说明可以通过运算得到 $24$。如果所有的可能性的结果都不等于 $24$，则说明无法通过运算得到 $24$。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 $24$ 时应考虑精度误差，这道题中，误差小于 $10^{-6}$ 可以认为是相等。
进行除法运算时，除数不能为 $0$，如果遇到除数为 $0$ 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 $0$ 时应考虑精度误差，这道题中，当一个数字的绝对值小于 $10^{-6}$ 时，可以认为该数字等于 $0$。
还有一个可以优化的点。
###Java
class Solution {
static final int TARGET = 24;
static final double EPSILON = 1e-6;
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return solve(list);
}
public boolean solve(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - TARGET) < EPSILON;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) {
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) {
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) {
if (Math.abs(list.get(j)) < EPSILON) {
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (solve(list2)) {
return true;
}
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}
###C++
class Solution {
public:
static constexpr int TARGET = 24;
static constexpr double EPSILON = 1e-6;
static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool judgePoint24(vector<int> &nums) {
vector<double> l;
for (const int &num : nums) {
l.emplace_back(static_cast<double>(num));
}
return solve(l);
}
bool solve(vector<double> &l) {
if (l.size() == 0) {
return false;
}
if (l.size() == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
vector<double> list2 = vector<double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.emplace_back(l[k]);
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.emplace_back(l[i] + l[j]);
} else if (k == MULTIPLY) {
list2.emplace_back(l[i] * l[j]);
} else if (k == SUBTRACT) {
list2.emplace_back(l[i] - l[j]);
} else if (k == DIVIDE) {
if (fabs(l[j]) < EPSILON) {
continue;
}
list2.emplace_back(l[i] / l[j]);
}
if (solve(list2)) {
return true;
}
list2.pop_back();
}
}
}
}
return false;
}
};
###C
const int TARGET = 24;
const double EPSILON = 1e-6;
const int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool solve(double *l, int l_len) {
if (l_len == 0) {
return false;
}
if (l_len == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l_len;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
double list2[20];
int l2_len = 0;
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2[l2_len++] = l[k];
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2[l2_len++] = l[i] + l[j];
} else if (k == MULTIPLY) {
list2[l2_len++] = l[i] * l[j];
} else if (k == SUBTRACT) {
list2[l2_len++] = l[i] - l[j];
} else if (k == DIVIDE) {
if (fabs(l[j]) < EPSILON) {
continue;
}
list2[l2_len++] = l[i] / l[j];
}
if (solve(list2, l2_len)) {
return true;
}
l2_len--;
}
}
}
}
return false;
}
bool judgePoint24(int *nums, int numsSize) {
double l[20];
int l_len = 0;
for (int i = 0; i < numsSize; i++) {
l[l_len++] = nums[i];
}
return solve(l, l_len);
}
###Python
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
def solve(nums: List[float]) -> bool:
if not nums:
return False
if len(nums) == 1:
return abs(nums[0] - TARGET) < EPSILON
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i != j:
newNums = list()
for k, z in enumerate(nums):
if k != i and k != j:
newNums.append(z)
for k in range(4):
if k < 2 and i > j:
continue
if k == ADD:
newNums.append(x + y)
elif k == MULTIPLY:
newNums.append(x * y)
elif k == SUBTRACT:
newNums.append(x - y)
elif k == DIVIDE:
if abs(y) < EPSILON:
continue
newNums.append(x / y)
if solve(newNums):
return True
newNums.pop()
return False
return solve(nums)
###golang
const (
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
)
func judgePoint24(nums []int) bool {
list := []float64{}
for _, num := range nums {
list = append(list, float64(num))
}
return solve(list)
}
func solve(list []float64) bool {
if len(list) == 0 {
return false
}
if len(list) == 1 {
return abs(list[0] - TARGET) < EPSILON
}
size := len(list)
for i := 0; i < size; i++ {
for j := 0; j < size; j++ {
if i != j {
list2 := []float64{}
for k := 0; k < size; k++ {
if k != i && k != j {
list2 = append(list2, list[k])
}
}
for k := 0; k < 4; k++ {
if k < 2 && i < j {
continue
}
switch k {
case ADD:
list2 = append(list2, list[i] + list[j])
case MULTIPLY:
list2 = append(list2, list[i] * list[j])
case SUBTRACT:
list2 = append(list2, list[i] - list[j])
case DIVIDE:
if abs(list[j]) < EPSILON {
continue
} else {
list2 = append(list2, list[i] / list[j])
}
}
if solve(list2) {
return true
}
list2 = list2[:len(list2) - 1]
}
}
}
}
return false
}
func abs(x float64) float64 {
if x < 0 {
return -x
}
return x
}
复杂度分析
时间复杂度：$O(1)$。一共有 $9216$ 种可能性，对于每种可能性，各项操作的时间复杂度都是 $O(1)$，因此总时间复杂度是 $O(1)$。
空间复杂度：$O(1)$。空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 $4$ 个数，所以递归调用的层数最多为 $4$，存储中间状态的列表最多包含 $4$ 个元素，因此空间复杂度为常数。
我们要解决的问题（原问题）是：
用「枚举选哪个」思考，即枚举我们获得多少分：
这些问题都是和原问题相似的、规模更小的子问题。
根据上面的讨论，定义 $f[i]$ 表示从 $i$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
在当前回合，我们等概率地发生以下 $\textit{\textit{maxPts}}$ 种事件：
由于上述 $\textit{\textit{maxPts}}$ 种事件互斥且等概率地被选择，因此最终到达闭区间 $[k,n]$ 的概率为上述 $\textit{\textit{maxPts}}$ 个状态值的平均值，即
$$
f[i] = \dfrac{f[i+1] + f[i+2] + f[i+3] + \dots + f[i+\textit{maxPts}]}{\textit{maxPts}}
$$
由于转移来源比 $i$ 大，所以要倒序枚举 $i$。
由于转移方程中的分子是一个长度固定为 $\textit{maxPts}$ 的连续子数组的元素和，所以可以用定长滑动窗口 $\mathcal{O}(1)$ 计算，原理讲解请看【套路】教你解决定长滑窗！适用于所有定长滑窗题目！
初始值：
答案：$f[0]$，即原问题。
问：为什么滑动窗口的计算顺序不是「入-计算-出」，而是「计算-入-出」？
答：当我们遍历到 $i$ 时，窗口的左端点是 $i+1$ 而不是 $i$。所以 $f[i]$ 并不在窗口中，得先把 $f[i]$ 计算出来，然后下个循环 $f[i]$ 才在窗口中。
注：$n$ 可以与 $k+\textit{maxPts}$ 取 $\min$，但测试发现这个优化不显著。
###py
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
f = [0.0] * (n + 1)
s = 0.0
for i in range(n, -1, -1):
f[i] = 1.0 if i >= k else s / maxPts
# 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
# 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i + maxPts <= n:
s -= f[i + maxPts]
return f[0]
###java
class Solution {
public double new21Game(int n, int k, int maxPts) {
double[] f = new double[n + 1];
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
}
}
###cpp
class Solution {
public:
double new21Game(int n, int k, int maxPts) {
vector<double> f(n + 1);
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
}
};
###c
double new21Game(int n, int k, int maxPts) {
double* f = malloc((n + 1) * sizeof(double));
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
double ans = f[0];
free(f);
return ans;
}
###go
func new21Game(n, k, maxPts int) float64 {
f := make([]float64, n+1)
s := 0.0
for i := n; i >= 0; i-- {
if i >= k {
f[i] = 1 // 初始值
} else {
f[i] = s / float64(maxPts)
}
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i+maxPts <= n {
s -= f[i+maxPts]
}
}
return f[0]
}
###js
var new21Game = function(n, k, maxPts) {
const f = new Array(n + 1).fill(0);
let s = 0;
for (let i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
};
###rust
impl Solution {
pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
let n = n as usize;
let k = k as usize;
let max_pts = max_pts as usize;
let mut f = vec![0.0; n + 1];
let mut s = 0.0;
for i in (0..=n).rev() {
f[i] = if i >= k { 1.0 } else { s / max_pts as f64 };
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if i + max_pts <= n {
s -= f[i + max_pts];
}
}
f[0]
}
}
见下面动态规划题单的「十五、概率/期望 DP」和「§11.1 前缀和优化 DP」。
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。
爱丽丝的分数不超过 n 的概率是多少？
与实际答案误差不超过 10-5 的答案将被视为正确答案。
示例 1：
输入：n = 10, k = 1, maxPts = 10 输出：1.00000 解释：爱丽丝得到一张牌，然后停止。
示例 2：
输入：n = 6, k = 1, maxPts = 10 输出：0.60000 解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
示例 3：
输入：n = 21, k = 17, maxPts = 10 输出：0.73278
提示：
0 <= k <= n <= 1041 <= maxPts <= 104老实说，一开始没懂题目意思，后面才知道是求爱丽丝的胜率。
规则是这样：
[1,W] 的牌中选择任意一张，这张牌是可以无限重复的，也就是说无论她取多少次，每次取到 2（假如 2 在 [1,W] 范围内）的概率都是 1/W;K，她就会抽牌，大于等于 K 时，就停止抽牌;N 时，她就获胜了，求她获胜的概率。假设 dp[x] 为她手上牌面为x时，能获胜的概率，那么这个概率应该是：dp[x]=1/w * (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+w])
因为抽取的牌面机会都是均等的，她能抽取的面值在 [1,W] 之间，所以将概率之和平均一下就是 dp[x] 的概率。
强插一段解释：
x代表爱丽丝手上的牌面值，dp[x]代表爱丽丝手上持有的牌面值为x时，她获胜的概率（游戏结束时她所持牌面值小于等于N的概率）。
这个概率是怎么来的？x分2种情况:
- 当x>=K时，爱丽丝会停止抽牌，这个时候游戏已经结束了，她是赢是输也已经确定了，所以此时赢的概率要么1，要么0
- 当x<K时，爱丽丝会继续抽牌，抽牌是有概率的，所以她是赢是输也有概率。
她能抽到的牌面值在[1,W]之间，所以抽完后她的牌面在[x+1,x+w]之间，因为每张牌机率均等，所以抽完后牌面在[x+1,x+w]之间的每个面值概率都是相等的，而假如我们已知当牌面是[x+1,x+w]的胜率(即dp[x+1]...dp[x+w]的值)，那么可以推导：dp[x]=1/w * dp[x+1]+ 1/w * dp[x+2] + 1/w * dp[x+3]...+ 1/w * dp[x+w]
这个实际上就是动态规划的状态转移方程，不过本例是反着来转移的。
x 最多能到 K-1，因为当大于等于 K 时，爱丽丝会停止抽牌，所以当游戏结束时，即爱丽丝停止抽牌时，她可能达到的最大牌面是 K+W-1，而一开始她的牌面是 0，所以我们用一个长度为 K+W 的 dp 数组来保存她在所有面值下的胜率。
最后 dp[0]，也就是最开始爱丽丝还没有抽牌，她的牌面为 0 时的胜率，这个就是我们的答案。
我将这个格子分成了 2 部分 [0,K-1] 和 [K,K+W-1]，区别就是 [0,K-1] 爱丽丝可以抽牌，[K,K+W-1] 时不能抽牌，那么不能抽牌时她获胜的概率是多少呢，此时已不能抽牌，要么赢要么输，很显然牌面小于等于N时，概率就是 1，大于 N 概率就是 0，所以先直接填满图中蓝色的格子。
接下来，从 K-1 开始填图中的橘色部分，这个值根据我们前面提到的计算方式，实际上就相当于它后面 W 个格子的总和除以 W，
这时聪明的你一定会想到不用每轮都累加的方法吧，用一个 s 变量来保存累加结果，而下一轮只是减去右边的格子，加上左边的格子即可。
所以这题你要做的就是，先初始化蓝色格子，然后从最右边的橘色格子开始，填到最左边的格子，就是这么简单，不仅简单，而且你连动态规划的思想都学会了。
相信这么厉害的你，看到这里给我点个赞一定不是件很困难的事吧。
###Python3
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
dp=[None]*(K+W)
s=0
for i in range(K,K+W): # 填蓝色的格子
dp[i] = 1 if i<=N else 0
s+=dp[i]
for i in range(K-1,-1,-1): # 填橘黄色格子
dp[i]=s/W
s=s-dp[i+W]+dp[i]
return dp[0]
时间复杂度=格子长度 $O(K+W)$
空间复杂度=格子长度 $O(K+W)$
