Appearance
高频动态规划
零钱兑换
零钱兑换
这题是典型的 动态规划 / 完全背包。
题目意思是：给你一些硬币面额 coins，每种硬币可以无限使用，问凑出 amount 最少需要几枚硬币。 如果凑不出来，返回 -1。
核心思路
定义：
dp[i] = 凑出金额 i 需要的最少硬币数初始化：
c
dp[0] = 0
其他 dp[i] = 一个很大的数状态转移：
c
dp[i] = min(dp[i], dp[i - coin] + 1)意思是：
如果我想凑出金额 i
我可以先凑出 i - coin
然后再加一枚 coin比如：
c
coins = [1, 2, 5]
amount = 11可以这样凑：
c
5 + 5 + 1 = 11所以答案是 3。
C# 代码
c
using System; // 引入 Math.Min 方法
public class Solution // 定义题解类
{ // 类开始
public int CoinChange(int[] coins, int amount) // 定义零钱兑换方法
{ // 方法开始
int max = amount + 1; // 设置一个不可能达到的大值，表示当前金额暂时无法凑出
int[] dp = new int[amount + 1]; // 创建 dp 数组，dp[i] 表示凑出金额 i 的最少硬币数
for (int i = 0; i <= amount; i++) // 遍历 0 到 amount 的所有金额
{ // 循环开始
dp[i] = max; // 先把每个金额都初始化成不可达
} // 循环结束
dp[0] = 0; // 凑出金额 0 不需要任何硬币
for (int i = 1; i <= amount; i++) // 从金额 1 开始逐步计算到 amount
{ // 金额循环开始
for (int j = 0; j < coins.Length; j++) // 枚举每一种硬币
{ // 硬币循环开始
int coin = coins[j]; // 取出当前硬币面额
if (i >= coin) // 如果当前金额 i 至少能放下这枚硬币
{ // 判断开始
dp[i] = Math.Min(dp[i], dp[i - coin] + 1); // 用“先凑 i - coin，再加一枚 coin”的方案更新 dp[i]
} // 判断结束
} // 硬币循环结束
} // 金额循环结束
if (dp[amount] == max) // 如果最终 amount 仍然是不可达状态
{ // 判断开始
return -1; // 说明无法用这些硬币凑出 amount
} // 判断结束
return dp[amount]; // 返回凑出 amount 所需的最少硬币数
} // 方法结束
} // 类结束复杂度
时间复杂度：O(amount * coins.Length)。 空间复杂度：O(amount)。
面试记忆
dp[i] 表示：凑出金额 i 的最少硬币数。 每次枚举一枚硬币 coin，尝试用：
c
dp[i - coin] + 1来更新 dp[i]。
编辑距离
编辑距离
编辑距离就是：把一个字符串变成另一个字符串，最少需要多少次操作。
每次可以做三种操作：
插入一个字符
删除一个字符
替换一个字符比如：
c
word1 = "horse"
word2 = "ros"最少需要 3 步。
核心思路
定义：
dp[i][j] = word1 的前 i 个字符，变成 word2 的前 j 个字符，最少需要几步初始化：
c
dp[i][0] = i
dp[0][j] = j因为：
c
word1 前 i 个字符变成空串，只能删除 i 次
空串变成 word2 前 j 个字符，只能插入 j 次状态转移：
c
如果 word1[i - 1] == word2[j - 1]
dp[i][j] = dp[i - 1][j - 1]如果最后一个字符不同：
c
删除：dp[i - 1][j] + 1
插入：dp[i][j - 1] + 1
替换：dp[i - 1][j - 1] + 1取三者最小。
C# 代码
c
using System; // 引入 Math.Min 方法
public class Solution // 定义题解类
{ // 类开始
public int MinDistance(string word1, string word2) // 定义计算编辑距离的方法
{ // 方法开始
int m = word1.Length; // 获取 word1 的长度
int n = word2.Length; // 获取 word2 的长度
int[,] dp = new int[m + 1, n + 1]; // 创建二维 dp 数组，dp[i,j] 表示两个前缀的最小编辑距离
for (int i = 0; i <= m; i++) // 初始化第一列
{ // 循环开始
dp[i, 0] = i; // word1 前 i 个字符变成空串，需要删除 i 次
} // 循环结束
for (int j = 0; j <= n; j++) // 初始化第一行
{ // 循环开始
dp[0, j] = j; // 空串变成 word2 前 j 个字符，需要插入 j 次
} // 循环结束
for (int i = 1; i <= m; i++) // 枚举 word1 的前缀长度
{ // 外层循环开始
for (int j = 1; j <= n; j++) // 枚举 word2 的前缀长度
{ // 内层循环开始
if (word1[i - 1] == word2[j - 1]) // 如果两个前缀的最后一个字符相同
{ // 判断开始
dp[i, j] = dp[i - 1, j - 1]; // 最后一个字符不用操作，直接继承左上角结果
} // 判断结束
else // 如果两个前缀的最后一个字符不同
{ // 分支开始
int deleteCost = dp[i - 1, j] + 1; // 删除 word1 当前最后一个字符的代价
int insertCost = dp[i, j - 1] + 1; // 给 word1 插入 word2 当前最后一个字符的代价
int replaceCost = dp[i - 1, j - 1] + 1; // 替换 word1 当前最后一个字符的代价
dp[i, j] = Math.Min(deleteCost, Math.Min(insertCost, replaceCost)); // 三种操作中取最小代价
} // 分支结束
} // 内层循环结束
} // 外层循环结束
return dp[m, n]; // 返回完整 word1 变成完整 word2 的最小编辑距离
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
CAUTION
dp[i][j] 就看两个字符串的前缀。 最后字符相同，看左上角。 最后字符不同，就从 删除、插入、替换 三种操作里选最小值再加 1。
不同路径
不同路径
这题是二维 DP 入门经典题。
机器人从左上角出发，只能：
向右走
向下走问走到右下角一共有多少种不同路径。
核心思路
定义：
c
dp[i][j] = 到达第 i 行第 j 列的路径数量因为机器人只能向右或向下，所以到达当前格子，只可能来自：
上方格子
左方格子所以状态转移是：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]第一行和第一列都只能沿着一条直线走，所以都是 1。
C# 代码
c
public class Solution // 定义题解类
{ // 类开始
public int UniquePaths(int m, int n) // 定义计算不同路径数量的方法
{ // 方法开始
int[,] dp = new int[m, n]; // 创建二维 dp 数组，dp[i,j] 表示到达第 i 行第 j 列的路径数
for (int i = 0; i < m; i++) // 遍历所有行
{ // 循环开始
dp[i, 0] = 1; // 第一列只能一直向下走，所以路径数都是 1
} // 循环结束
for (int j = 0; j < n; j++) // 遍历所有列
{ // 循环开始
dp[0, j] = 1; // 第一行只能一直向右走，所以路径数都是 1
} // 循环结束
for (int i = 1; i < m; i++) // 从第二行开始计算
{ // 外层循环开始
for (int j = 1; j < n; j++) // 从第二列开始计算
{ // 内层循环开始
dp[i, j] = dp[i - 1, j] + dp[i, j - 1]; // 当前格子的路径数等于上方路径数加左方路径数
} // 内层循环结束
} // 外层循环结束
return dp[m - 1, n - 1]; // 返回右下角的路径数量
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
这题记一句话就够了：
到达当前格子的路径数 = 上方格子的路径数 + 左方格子的路径数第一行、第一列初始化为 1，因为它们都只有一种走法。
最小路径和
最小路径和
这题和「不同路径」很像，只不过：
不同路径：统计有多少条路
最小路径和：统计最便宜的一条路机器人从左上角走到右下角，只能向右或向下，每经过一个格子都要加上格子的数字，求最小总和。
核心思路
定义：
dp[i][j] = 从左上角走到 grid[i][j] 的最小路径和因为只能向右或向下，所以到达当前格子，只可能来自：
上方格子
左方格子状态转移：
c
dp[i][j] = grid[i][j] + Min(dp[i - 1][j], dp[i][j - 1])第一行只能从左边一路走过来。 第一列只能从上边一路走下来。
C# 代码
c
using System; // 引入 Math.Min 方法
public class Solution // 定义题解类
{ // 类开始
public int MinPathSum(int[][] grid) // 定义计算最小路径和的方法
{ // 方法开始
int m = grid.Length; // 获取网格的行数
int n = grid[0].Length; // 获取网格的列数
int[,] dp = new int[m, n]; // 创建二维 dp 数组，dp[i,j] 表示走到当前位置的最小路径和
dp[0, 0] = grid[0][0]; // 起点的最小路径和就是起点自己的值
for (int i = 1; i < m; i++) // 初始化第一列
{ // 循环开始
dp[i, 0] = dp[i - 1, 0] + grid[i][0]; // 第一列只能从上往下走，所以只能累加上方路径和
} // 循环结束
for (int j = 1; j < n; j++) // 初始化第一行
{ // 循环开始
dp[0, j] = dp[0, j - 1] + grid[0][j]; // 第一行只能从左往右走，所以只能累加左方路径和
} // 循环结束
for (int i = 1; i < m; i++) // 从第二行开始遍历
{ // 外层循环开始
for (int j = 1; j < n; j++) // 从第二列开始遍历
{ // 内层循环开始
int fromTop = dp[i - 1, j]; // 记录从上方格子走过来的最小路径和
int fromLeft = dp[i, j - 1]; // 记录从左方格子走过来的最小路径和
dp[i, j] = grid[i][j] + Math.Min(fromTop, fromLeft); // 当前最小路径和等于当前格子值加上上方和左方的较小值
} // 内层循环结束
} // 外层循环结束
return dp[m - 1, n - 1]; // 返回右下角的最小路径和
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
到达当前格子的最小路径和：
当前格子数字 + Min(上方最小路径和, 左方最小路径和)只要你记住“只能从上或左来”，这题就很顺。
分割等和子集
分割等和子集
这题本质是：0/1 背包 + 子集和问题。
题目问：能不能把数组分成两个子集，让它们的和相等。
换句话说，如果数组总和是 sum，那我们只需要判断：
能不能从数组里选一些数，凑出 sum / 2
核心思路
先算总和：
sum = 所有数字之和如果 sum 是奇数，直接返回 false，因为奇数不可能平均分成两份。
如果 sum 是偶数：
c
target = sum / 2接下来问题变成：
能不能选一些数字，刚好凑出 target？定义：
dp[j] = 是否能凑出和 j状态转移：
c
dp[j] = dp[j] || dp[j - num]意思是：
如果之前能凑出 j - num
那现在加上 num，就能凑出 jC# 代码
c
public class Solution // 定义题解类
{ // 类开始
public bool CanPartition(int[] nums) // 定义判断是否能分割成两个等和子集的方法
{ // 方法开始
int sum = 0; // 定义总和变量
for (int i = 0; i < nums.Length; i++) // 遍历数组中的每个数字
{ // 循环开始
sum += nums[i]; // 把当前数字累加到总和里
} // 循环结束
if (sum % 2 != 0) // 如果总和是奇数
{ // 判断开始
return false; // 奇数无法平均分成两个整数和子集
} // 判断结束
int target = sum / 2; // 目标就是总和的一半
bool[] dp = new bool[target + 1]; // 创建 dp 数组，dp[j] 表示是否能凑出和 j
dp[0] = true; // 凑出 0 不需要选择任何数字，所以一定可以
for (int i = 0; i < nums.Length; i++) // 遍历每一个数字
{ // 外层循环开始
int num = nums[i]; // 取出当前数字
for (int j = target; j >= num; j--) // 从 target 倒序遍历到 num，保证当前数字只使用一次
{ // 内层循环开始
dp[j] = dp[j] || dp[j - num]; // 如果之前能凑出 j - num，现在加上 num 就能凑出 j
} // 内层循环结束
} // 外层循环结束
return dp[target]; // 返回是否能凑出目标和
} // 方法结束
} // 类结束为什么要倒序遍历？
因为每个数字只能用一次。
如果正序遍历，可能会出现这种问题：
c
当前数字是 5
刚更新出 dp[5]
下一步又用同一个 5 更新 dp[10]这样就等于同一个数字被用了多次，变成完全背包了。
所以 0/1 背包要倒序：
c
for j = target 到 num复杂度
时间复杂度：O(n * target)。 空间复杂度：O(target)。
面试记忆
先判断总和是不是偶数。 然后用 0/1 背包判断能不能凑出 sum / 2。 最关键一句：每个数只能用一次，所以容量必须倒序遍历。
最长回文子序列
最长回文子序列
最长回文子序列和最长回文子串不一样：
子串：必须连续
子序列：可以不连续，但相对顺序不能变比如：
c
s = "bbbab"最长回文子序列可以选：
c
b b b b跳过中间的 a，所以答案是 4。
核心思路
定义：
dp[i][j] = s[i..j] 这个区间里的最长回文子序列长度如果首尾字符相等：
c
s[i] == s[j]
dp[i][j] = dp[i + 1][j - 1] + 2意思是：中间区间的最长回文子序列，再把左右两个相同字符包起来。
如果首尾字符不相等：
c
s[i] != s[j]
dp[i][j] = Max(dp[i + 1][j], dp[i][j - 1])意思是：左端和右端不能同时选，那就尝试跳过左端或者跳过右端，取更长的那个。
C# 代码
c
using System; // 引入 Math.Max 方法
public class Solution // 定义题解类
{ // 类开始
public int LongestPalindromeSubseq(string s) // 定义求最长回文子序列长度的方法
{ // 方法开始
int n = s.Length; // 获取字符串长度
if (n == 0) // 如果字符串为空
{ // 判断开始
return 0; // 空字符串的最长回文子序列长度是 0
} // 判断结束
int[,] dp = new int[n, n]; // 创建二维 dp 数组，dp[i,j] 表示 s[i..j] 的最长回文子序列长度
for (int i = n - 1; i >= 0; i--) // i 从右往左遍历，保证依赖的子区间已经算好
{ // 外层循环开始
dp[i, i] = 1; // 单个字符本身就是回文，长度为 1
for (int j = i + 1; j < n; j++) // j 从 i 右边开始往右遍历
{ // 内层循环开始
if (s[i] == s[j]) // 如果区间左右两端字符相同
{ // 判断开始
dp[i, j] = dp[i + 1, j - 1] + 2; // 中间回文长度加上左右两个相同字符
} // 判断结束
else // 如果区间左右两端字符不同
{ // 分支开始
dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]); // 跳过左端或跳过右端，取较大值
} // 分支结束
} // 内层循环结束
} // 外层循环结束
return dp[0, n - 1]; // 返回整个字符串区间的最长回文子序列长度
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n * n)。 空间复杂度：O(n * n)。
面试记忆
这是典型 区间 DP。 dp[i][j] 看的是区间 s[i..j]：
首尾相等：中间 + 2
首尾不等：跳左 / 跳右，取最大正则匹配
正则匹配
这里的正则匹配一般指 LeetCode 经典版本，只支持两个特殊符号：
. 匹配任意一个字符
* 表示前一个字符出现 0 次或多次注意：它要求 整个字符串完整匹配，不是包含某个子串。
核心思路
定义：
dp[i][j] = s 的前 i 个字符，能否匹配 p 的前 j 个字符如果当前模式字符是普通字符或 .：
c
dp[i][j] = dp[i - 1][j - 1]如果当前模式字符是 *，它有两种选择：
c
匹配 0 次：dp[i][j] = dp[i][j - 2]
匹配多次：dp[i][j] = dp[i - 1][j]C# 代码
c
public class Solution // 定义题解类
{ // 类开始
public bool IsMatch(string s, string p) // 定义正则匹配方法
{ // 方法开始
int m = s.Length; // 获取字符串 s 的长度
int n = p.Length; // 获取模式串 p 的长度
bool[,] dp = new bool[m + 1, n + 1]; // 创建 dp 数组，dp[i,j] 表示 s 前 i 个字符和 p 前 j 个字符是否匹配
dp[0, 0] = true; // 空字符串和空模式可以匹配
for (int j = 2; j <= n; j++) // 初始化空字符串和模式串的匹配情况
{ // 循环开始
if (p[j - 1] == '*') // 如果当前模式字符是星号
{ // 判断开始
dp[0, j] = dp[0, j - 2]; // 星号让前一个字符出现 0 次，所以可以丢掉前字符和星号
} // 判断结束
} // 循环结束
for (int i = 1; i <= m; i++) // 遍历字符串 s 的每个前缀长度
{ // 外层循环开始
for (int j = 1; j <= n; j++) // 遍历模式串 p 的每个前缀长度
{ // 内层循环开始
if (p[j - 1] == s[i - 1] || p[j - 1] == '.') // 如果当前字符相同，或者模式字符是点号
{ // 判断开始
dp[i, j] = dp[i - 1, j - 1]; // 当前字符匹配，结果取决于前面的字符是否匹配
} // 判断结束
else if (p[j - 1] == '*' && j >= 2) // 如果当前模式字符是星号，并且前面存在可修饰字符
{ // 星号判断开始
dp[i, j] = dp[i, j - 2]; // 情况一：星号匹配 0 次，直接丢掉前一个字符和星号
char previousPatternChar = p[j - 2]; // 取出星号修饰的前一个模式字符
if (previousPatternChar == s[i - 1] || previousPatternChar == '.') // 如果前一个模式字符能匹配当前 s 字符
{ // 多次匹配判断开始
dp[i, j] = dp[i, j] || dp[i - 1, j]; // 情况二：星号匹配多次，继续消耗 s 的一个字符
} // 多次匹配判断结束
} // 星号判断结束
} // 内层循环结束
} // 外层循环结束
return dp[m, n]; // 返回完整字符串和完整模式是否匹配
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
普通字符和 .：看左上角。 遇到 *：两种选择。
c
不用前一个字符：dp[i][j - 2]
继续匹配当前字符：dp[i - 1][j]股票含冷冻期
股票含冷冻期
这题是股票 DP 里很经典的 状态机 DP。
题目规则是：
可以买入
可以卖出
可以休息
但是卖出后的第二天不能买入比如：
prices = [1, 2, 3, 0, 2]最优操作是：
day0 买入，价格 1
day1 卖出，价格 2，利润 1
day2 冷冻，不能买
day3 买入，价格 0
day4 卖出，价格 2，利润 2总利润：
1 + 2 = 3
核心思路
每天结束后，我们只关心三种状态：
hold：手里持有股票
sold：今天刚卖出股票
rest：手里没有股票，并且不是今天刚卖状态转移：
c
hold = Max(昨天 hold, 昨天 rest - 今天价格)
sold = 昨天 hold + 今天价格
rest = Max(昨天 rest, 昨天 sold)注意最关键的一点：
买入只能从 rest 来，不能从 sold 来因为 sold 表示昨天刚卖，今天是冷冻期。
C# 代码
c
using System; // 引入 Math.Max 方法
public class Solution // 定义题解类
{ // 类开始
public int MaxProfit(int[] prices) // 定义计算最大利润的方法
{ // 方法开始
if (prices == null || prices.Length == 0) // 如果价格数组为空
{ // 判断开始
return 0; // 没有价格就无法交易，利润为 0
} // 判断结束
int hold = -prices[0]; // hold 表示当天结束后持有股票的最大利润，第一天买入就是负价格
int sold = 0; // sold 表示当天刚卖出股票的最大利润，初始还没卖所以为 0
int rest = 0; // rest 表示当天结束后空仓休息的最大利润，初始为 0
for (int i = 1; i < prices.Length; i++) // 从第二天开始遍历价格
{ // 循环开始
int oldHold = hold; // 保存昨天的 hold，避免更新后影响其他状态
int oldSold = sold; // 保存昨天的 sold，表示昨天刚卖出的状态
int oldRest = rest; // 保存昨天的 rest，表示昨天空仓且可以买入的状态
hold = Math.Max(oldHold, oldRest - prices[i]); // 今天持股：要么昨天就持股，要么昨天休息今天买入
sold = oldHold + prices[i]; // 今天刚卖：只能从昨天持股状态卖出
rest = Math.Max(oldRest, oldSold); // 今天休息：要么昨天也休息，要么昨天刚卖今天进入冷冻后的空仓状态
} // 循环结束
return Math.Max(sold, rest); // 最后一天结束时不能要求手里还持股，所以在 sold 和 rest 中取最大
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n)。 空间复杂度：O(1)。
面试记忆
这题不要只想“今天买还是卖”。 要按状态想：
hold：持股
sold：今天刚卖
rest：空仓可买最关键一句：卖出后有冷冻期，所以买入只能从 rest 状态转移到 hold。
戳气球
戳气球
这题是经典 区间 DP。
最重要的思路是：不要想第一个戳谁，要想最后戳谁。
因为如果你想第一个戳谁，左右邻居会一直变化，很难确定收益。 但如果你想“区间里最后戳 k”，那么它左右两边的边界 left 和 right 一定还没被戳，收益就固定了：
c
values[left] * values[k] * values[right]
核心思路
原数组：
c
nums = [3, 1, 5, 8]先在两边补 1：
c
values = [1, 3, 1, 5, 8, 1]定义：
c
dp[left][right] = 戳破 left 和 right 中间所有气球，能获得的最大金币注意这是 开区间：
c
(left, right)也就是 left 和 right 不戳，只戳它们中间的气球。
状态转移：
c
dp[left][right] =
max(
dp[left][k]
+ values[left] * values[k] * values[right]
+ dp[k][right]
)其中 k 表示：在 (left, right) 这个区间里，最后一个被戳破的气球。
C# 代码
c
public class Solution // 定义题解类
{ // 类开始
public int MaxCoins(int[] nums) // 定义计算戳气球最大金币数的方法
{ // 方法开始
int n = nums.Length; // 获取原始气球数量
int[] values = new int[n + 2]; // 创建新数组，用来在左右两边补虚拟气球 1
values[0] = 1; // 左边界虚拟气球的值是 1
values[n + 1] = 1; // 右边界虚拟气球的值是 1
for (int i = 0; i < n; i++) // 遍历原始气球数组
{ // 循环开始
values[i + 1] = nums[i]; // 把原始气球复制到新数组中间
} // 循环结束
int[,] dp = new int[n + 2, n + 2]; // 创建区间 dp 数组，dp[left,right] 表示戳完开区间内气球的最大金币
for (int length = 2; length <= n + 1; length++) // 枚举区间长度，长度至少为 2 才可能有中间气球
{ // 区间长度循环开始
for (int left = 0; left + length <= n + 1; left++) // 枚举左边界
{ // 左边界循环开始
int right = left + length; // 根据左边界和区间长度得到右边界
for (int k = left + 1; k < right; k++) // 枚举最后一个被戳破的气球 k
{ // 枚举 k 循环开始
int coins = dp[left, k] + values[left] * values[k] * values[right] + dp[k, right]; // 计算最后戳 k 时的总金币
dp[left, right] = System.Math.Max(dp[left, right], coins); // 用当前方案更新最大金币数
} // 枚举 k 循环结束
} // 左边界循环结束
} // 区间长度循环结束
return dp[0, n + 1]; // 返回戳完所有真实气球后的最大金币数
} // 方法结束
} // 类结束复杂度
时间复杂度：O(n^3)，因为要枚举区间长度、左边界、最后戳的气球 k。 空间复杂度：O(n^2)，因为用了二维 dp 数组。
面试记忆
戳气球的关键不是“先戳谁”，而是：
这个区间里最后戳谁？最后戳 k 时，左右边界固定，所以收益固定；再加上左右两个小区间的最优解。
最大正方形
最大正方形
这题是二维 DP，题目意思是：在一个只包含 '0' 和 '1' 的矩阵里，找出只包含 '1' 的最大正方形，返回它的面积。
注意返回的是 面积，不是边长。
核心思路
定义：
c
dp[i][j] = 以 matrix[i][j] 为右下角，能形成的最大正方形边长如果当前位置是 '0'：
c
dp[i][j] = 0如果当前位置是 '1'：
dp[i][j] = Min(上方, 左方, 左上方) + 1也就是：
c
dp[i][j] = Min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1因为一个正方形想扩大，必须保证：
上边能撑住
左边能撑住
左上角也能撑住C# 代码
c
using System; // 引入 Math.Min 和 Math.Max 方法
public class Solution // 定义题解类
{ // 类开始
public int MaximalSquare(char[][] matrix) // 定义求最大正方形面积的方法
{ // 方法开始
if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) // 如果矩阵为空
{ // 判断开始
return 0; // 空矩阵没有正方形，返回 0
} // 判断结束
int m = matrix.Length; // 获取矩阵行数
int n = matrix[0].Length; // 获取矩阵列数
int[,] dp = new int[m, n]; // 创建 dp 数组，dp[i,j] 表示以当前位置为右下角的最大正方形边长
int maxSide = 0; // 记录目前遇到的最大正方形边长
for (int i = 0; i < m; i++) // 遍历每一行
{ // 外层循环开始
for (int j = 0; j < n; j++) // 遍历每一列
{ // 内层循环开始
if (matrix[i][j] == '1') // 如果当前格子是 1
{ // 判断开始
if (i == 0 || j == 0) // 如果当前格子在第一行或第一列
{ // 边界判断开始
dp[i, j] = 1; // 边界上的 1 只能形成边长为 1 的正方形
} // 边界判断结束
else // 如果当前格子不在边界
{ // 分支开始
int top = dp[i - 1, j]; // 获取上方格子的最大边长
int left = dp[i, j - 1]; // 获取左方格子的最大边长
int topLeft = dp[i - 1, j - 1]; // 获取左上方格子的最大边长
dp[i, j] = Math.Min(topLeft, Math.Min(top, left)) + 1; // 当前边长等于三个方向最小值加一
} // 分支结束
maxSide = Math.Max(maxSide, dp[i, j]); // 更新最大正方形边长
} // 判断结束
} // 内层循环结束
} // 外层循环结束
return maxSide * maxSide; // 返回最大正方形面积
} // 方法结束
} // 类结束复杂度
时间复杂度：O(m * n)。 空间复杂度：O(m * n)。
面试记忆
dp[i][j] 不是统计有多少个 1，而是：
以当前位置为右下角的最大正方形边长当前位置是 1 时，看 上、左、左上 三个方向的最小值再加 1。