72. 编辑距离
221. 最大正方形
5. 最长回文子串
300. 最长上升子序列
53. 最大(连续)子序和 / 最大子数组和
152. 乘积最大(连续)子序列 / 最大子数组积
198. 打家劫舍
322. 零钱兑换
518. 零钱兑换 II
10. 正则表达式匹配
139. 单词拆分
140. 单词拆分 II
![]()
image
image
72. 编辑距离
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
### DP：空间优化成一维数组
n1=len(word1)+1
n2=len(word2)+1
dp=list(range(n2)) ###动态更新，某一行的所有列的dp结果 #初始化同时也是第0行的dp数组
for i in range(1, n1): #行间更新
# 1.暂存前一行的dp[0]用于后面初始化本行的对角diagonal_num
temp=dp[0] #表示上一行左斜对角的dp值，在此初始化为第0行的dp[0]
# 2.根据需要看每一行的dp[0],是否需要初始化
###这里每一行dp[0]必须初始化是因为每一行的dp[0]依赖于上一行的dp[0]的值
###从二维dp的矩阵中看到，每一行的dp[0]是要等于上一行的dp[0]+1 (正好就是i)， 相当于n1变长的过程中，需要dp[0]步删除操作才能变成n2(此时为空字符串)
dp[0]=i
for j in range(1,n2): #行内更新 （从第一行开始更新）
diagonal_num=temp ###每次从上一行的dp[0]开始
temp=dp[j] ###dp[j]还是上一行的第j列的值（最开始从0行的0列值开始），为了更新本行下一个元素的的diagonal_num
if word1[i-1]==word2[j-1]:
dp[j] = diagonal_num
else:
dp[j] = 1 + min(dp[j], dp[j-1], diagonal_num) #min()里的dp[j]还是上一行的第j列的值，dp[j-1]已经更新成本行的值了
return dp[-1]
### DP: 二维数组
n1=len(word1)+1
n2=len(word2)+1
dp=[[0]*n2 for _ in range(n1)]
###初始化：当其中一个str1 为空时，要将其变成另一个非空的str2就需要每步插入一个字符（每次操作数递增1）
for i in range(1, n1):
dp[i][0]=dp[i-1][0]+1
for j in range(1, n2):
dp[0][j]=dp[0][j-1]+1
for i in range(1, n1):
for j in range(1,n2):
if word1[i-1]==word2[j-1]:
dp[i][j] = dp[i-1][j-1] ###元素一样了，无操作
else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
#分别对应：
### word1[i] 替换成 word2[j]
### word1 后面插入(append) word2[j]
### word1 后面删除(pop) word1[i]
return dp[-1][-1]
221. 最大正方形
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
### DP: 优化成一维数组的解法 (为何空间占用没有降下来太多？？？)
if not matrix:
return 0
row=len(matrix)+1 #行
column=len(matrix[0])+1
dp=[ 0 for _ in range(column)]###比原矩阵多一列，主要是位置0每次都是一个占位/初始化为0，当前行仅仅用到上一行的结果，所以每行的结果由之前的结果动态更新
max_len=0
for i in range(1, row):
temp=dp[0] #（用到斜上对角处的dp值时基本都需要这句）暂存上一行的dp[0],为了初始化每一行的diagonal_len
###这里dp[0]并不用初始化是因为每一行的dp[0]并不依赖于上一行的dp[0]的值，dp[0]不会改变一直为0（为了占位）
for j in range(1, column):
diagonal_len=temp ###从上一行的dp[0]一直更新到dp[column-1]
temp=dp[j] ###现在的dp还是上一行的值，这里是为了更新diagonal_len到上一行的下一个值，此时对于本行下一列dp结果而言，对角dp就变成了本行上一行当前列的dp结果
if matrix[i-1][j-1]=='1':
dp[j] = 1 + min(dp[j], diagonal_len, dp[j-1]) #min()中的 dp[j]是上一行对应列的dp如果，而dp[j-1]此时已经是(上一个j)更新后的本行前一列的dp结果
max_len=max(max_len, dp[j])######放这儿对本题没有影响，而且会减少判断次数
else:
dp[j]=0 #dp数组优化成一行后该句不能省，因为本行j处的dp值会因为该处元素是否为”1“而变化（上一行j处为”1“本行可能就变成”0“），无论怎样dp[j]都需要更新
return max_len*max_len
### DP（木桶的短板理论）: 二维数组的解法
if not matrix: ###一定在最开始要加上这个异常判断，否则就不通过（而且后面的len(matrix）也会报错）
return 0
row=len(matrix)+1
column=len(matrix[0])+1
dp=[[0]*(column) for _ in range(row)] #dp[i][j]：以点matrix[i-1][j-1]为正方形右下角时最大的正方形边长
max_len=0 #因为是正方形，所以能找到最大边长就可以
for i in range(1, row):
for j in range(1, column):
if matrix[i-1][j-1]=='1': #因为遍历从 1 开始（0号位置用作初始状态），所以当前位置为（i-1,j-1）
dp[i][j]=min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1
max_len=max(max_len, dp[i][j]) #更新全局的最大边长
return max_len*max_len
5.最长回文子串
class Solution:
def longestPalindrome(self, s: str) -> str:
### 关键是需要利用dp数组辅助得到 start_index和max_len
if(not s or len(s)==1):
return s
n=len(s)
dp=[[False]*n for _ in range(n)] #实际上一个下三角矩阵就行(对称), dp[i][j]表示s[i:j]是否为回文串
start, max_len = 0, 1 #初始化最长回文子串的开始索引start， 最长长度max_len=1
for i in range(n):
dp[i][i]=True #所有单个字符都是回文串
if(i<n-1 and s[i]==s[i+1]): #若两相邻的字符相同，则将这两个字符对应的位置的dp都置为True
dp[i][i+1]=True
start, max_len = i, 2
for l in range(3,n+1): #回文子串的长度 l 再从3开始探索
for i in range(n+1-l): #从str的0号位置开始探索长度为3往上是否有回文子串，由 i+l-1=n得 i=n+1-l
r=i+l-1
if s[i]==s[r] and dp[i+1][r-1]: #若首尾两个字符i,r相同且去掉首尾字符后的子串仍为回文串则说明str[i:r]也是回文串
dp[i][r]=True
start, max_len = i, l #因为每次都更新最长回文子串的开始索引start，所以最终该方法得到的最长回文子串是位置比较靠后的那个答案
return s[start : start+max_len]
300. 最长上升子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
'''
正常的动态规划： O(N^2)， 或者和sorted(nums)求LCS即可
dp[i]: 表示在以arr[i]这个数结尾(最长的不一定以arr[i]结尾，所以求得时全局的dp最大值)的情况下， arr[0...i]中最大递增子序列的长度
dp[0]=1
dp[i]=max{dp[j]+1 (0<=j<i, arr[j]<arr[i])}
'''
if not nums:
return 0
n=len(nums)
dp=[1]*n #dp[i] 所有元素置 11，含义是每个元素都至少可以单独成为子序列，此时长度都为 11
for i in range(1, n): #dp[0]可确定为1，从dp[1]开始算
for j in range(0, i): #在index=i之前的元素都要查查看
if nums[j]<nums[i]: #如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
dp[i]=max(dp[i], dp[j]+1)
return max(dp)
'''
贪心 + 二分查找： 时间 O(NlogN) ，遍历 nums 列表需O(N)，在每个nums[i] 二分法需O(logN)
建立一个临时空数组tmp（用于存放一组最长上升子列，模拟其生成过程）
首先将arr[0]插入tmp中，然后遍历arr[1:]
1. 如果遍历到的元素val <= tmp[0]，更新tmp[0]=val（也就是遍历到的元素比最长上升子序列中的最小元素小，我们通过贪心的策略，当然是越小越好，所以替换之前元素）
2. 如果tmp[0] < val <= tmp[-1]，通过二分搜索法找到tmp中从左到右第一个>=val的元素位置，然后用val替换掉它（和上面的做法相同）
3、如果tmp[-1] < val，我们更新tmp.append(val)（也就是新加入的元素比最长上升子序列中的最后一个元素大，那么必然构成解）
上面3步其实就是模拟将arr[i]插入到tmp数组中的过程，可以用二分查找来做O(log(N))
最后len(tmp)就是LIS的长度
'''
# dp=[1]*len(nums) #dp[i]等于arr[i] 按照上面的方式 "插入"到tmp数组中的位置的index+1
from bisect import bisect_left
tmp=[]
for i in range(len(nums)):
index=bisect_left(tmp, nums[i]) #二分查找,返回nums[i]能插入到tmp中的位置索引，若比最后一个元素还要大，则直接插在tmp最后，此时会返回 “tmp最大的索引+1” (即len(tmp))
# dp[i]=index+1
if index==len(tmp): # nums[i] > tmp[-1] ,nums[i]插入到tmp的最后
tmp.append(nums[i])
else:
tmp[index]=nums[i]
return len(tmp) #也就是最长递增子序列的长度
# tmp = []
# for num in nums:
# #二分查找实现
# low, upper = 0, len(tmp) #需要首尾两个指针
# while low < upper:
# mid = (upper - low)//2 + low
# if tmp[mid] < num:
# low = mid + 1
# else:
# upper = mid
# #upper就是nums[i]可以插入进tmp的index
# if upper == len(tmp):
# tmp.append(num)
# else:
# tmp[upper] = num
# return len(tmp)
53. 最大子序和
分治法图解
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
'''
贪心算法：（注意子数组是连续的，可能会很长，中间有正有负，不是说遇到负值就停下来）
使用单个数组作为输入来查找最大（或最小）元素（或总和）的问题，贪心算法是可以在线性时间解决的方法之一。
每一步都选择最佳方案，遍历数组并在每个步骤中更新：
当前元素
当前元素位置的最大和 :
迄今为止的最大和
'''
curr_sum = max_sum = nums[0] #curr_sum：只考虑当前位置时可以得到的最大子数组和
#当前面一个元素的curr_sum>0时，当前元素值可以选择加上前面一个元素的curr_sum, 否则就不要前面的元素了从当前nums[i]重新开始）
for i in range(1,len(nums)):
curr_sum = max(nums[i]+curr_sum, nums[i]) #看看前面的结果是否可以带来正收益，是就更新，计算当前位置所能得到的最大和
max_sum=max(max_sum, curr_sum)
return max_sum
'''
动态规划
'''
max_sum = nums[0]
for i in range(1, len(nums)):
if nums[i - 1] > 0: #看看前面的结果是否可以带来正收益，是就更新
nums[i] += nums[i - 1] #原地更新数组，使nums[i]变成curr_sum, 和上面的贪心方法实际一样
max_sum = max(nums[i], max_sum)
return max_sum
'''
分治法：
定义基本情况。
将问题分解为子问题并递归地解决它们。
合并子问题的解以获得原始问题的解。
时间复杂度： O(NlogN)。
空间复杂度： O(logN)，递归时栈使用的空间。
'''
n = len(nums)
#确定递归终止条件
if n == 1:
return nums[0]
else:
#递归计算左半边最大子序和
max_left = self.maxSubArray(nums[0 : len(nums)//2])
#递归计算右半边最大子序和
max_right = self.maxSubArray(nums[len(nums)//2 : len(nums)])
#计算包括中间元素的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加
max_l = nums[len(nums)//2 - 1]
tmp = 0
for i in range(len(nums)//2 - 1, -1, -1):
tmp += nums[i]
max_l = max(tmp, max_l) #获取一直”连续“往左走时，能获得的最大累加和
max_r = nums[len(nums)//2] ###
tmp = 0
for i in range(len(nums)//2, len(nums)):
tmp += nums[i]
max_r = max(tmp, max_r)
#返回以上三种情况中的最大值
return max(max_right, max_left, max_l+max_r)
152. 乘积最大子序列
解法一：动态规划
解法二：
class Solution:
def maxProduct(self, nums: List[int]) -> int:
'''
空间优化后（O(N)->O(1), 只用到上面一个元素的dpMax和dpMin) 的动态规划：和 53.子数组最大的和的思路差不多但需要同时记录最大和最小值(可能是一个绝对值很大的负数)
根据上面的分析，一个包含nums[i]的子数组最大乘积只可能等于 dpMax*num, dpMin*num, num 这三种情况
'''
dpMax = dpMin = max_mul = nums[0] #必须先初始化为nums[0]因为这样还涵盖了数组只有一个元素的情况
for i in range(1, len(nums)): #从nums[1]开始遍历，nums[0]处的就是
tmp = dpMax #更新 dpMin 的时候需要用到的是之前的dpMax，所以先暂存一下之前的dpMax
dpMax = max(dpMin*nums[i], dpMax*nums[i], nums[i])
dpMin = min(dpMin*nums[i], tmp*nums[i], nums[i])
max_mul = max(max_mul, dpMax)
return max_mul
'''
”保证一个连续序列里有偶数个负数且最长就可以得到最大乘积“
可以看成求被0拆分的各个子数组的最大值。
当一个数组中没有0存在，则分为两种情况：
1.负数为偶数个，则整个数组的各个值相乘为最大值；
2.负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，从右边也有一个“最大值”，比较，得出最大值。
'''
# 包含了所有数相乘的情况
### 奇数个负数的情况一： 正向遍历
max_mul=1
res=nums[0]
for i in range(len(nums)):
max_mul*=nums[i]
res=max(res, max_mul)
# 如果有 0 存在的话，会使得上边的代码到 0 的位置之后 max_mul 就一直变成 0
# 所以把数组看成几个都不含有 0 的子数组进行解决即可。
# 代码中，我们只需要在遇到零的时候，把 max_mul 再初始化为 1 即可
max_mul = 1 if max_mul==0 else max_mul #遇到0就从1重新开始，相当于数列被0隔断
### 奇数个负数的情况二： 反向遍历
max_mul=1
for i in range(len(nums)-1, -1, -1):
max_mul*=nums[i]
res=max(res, max_mul)
max_mul = 1 if max_mul==0 else max_mul
return res
'''上面的简洁写法，先得到翻转后的数组（增大了空间复杂度）'''
nums_r = nums[::-1] #
for i in range(1, len(nums)):
nums[i] *= nums[i - 1] or 1 #python中： 0 or 1 = 1 , 不等于0的数x or 1 = x
nums_r[i] *= nums_r[i - 1] or 1
return max(max(nums), max(nums_r))
198. 打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
'''
普通动态规划： dp[i], 偷到第i户时可以获得的最高金额（选， 不选）
”非连续的累积问题可以考虑到某个位置选或不选的解题方向“，而53和152都要求连续顾不可以这样考虑
'''
if not nums:
return 0
n = len(nums)
dp = [0]*(n+1) #dp前面多一个占位0（这样可以涵盖nums内只有一个元素的情况）
dp[0]=0
dp[1]=nums[0]
for i in range(2, n+1):
#因为dp数组要从dp[2]开始算了，但此时nums数组应首先考虑nums[1], 所以当前遍历到的元素应该为nums[i-1]
dp[i] = max(dp[i-2]+nums[i-1], dp[i-1])
return dp[-1]
'''
优化空间后的动态规划
'''
pre1, pre2 = 0, 0 #开始全都初始化为0就可以涵盖 nums内无元素或只有一个元素的情况
for num in nums:
tmp = pre2 #保存当前的pre2用于之后更新pre1
pre2 = max(pre1+num, pre2)
pre1 = tmp
return pre2
322. 零钱兑换
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
'''
时间复杂度：O(Sn)，其中 S 是金额，n 是面额种类数。一共需要计算 O(S) 个状态，S 为题目所给的总金额。
对于每个状态，每次需要枚举 n 种面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。DP 数组需要开长度为总金额 S 的空间。
'''
dp = [float('inf')] * (amount + 1) #dp[i]表示组成金额 i 所需最少的硬币数量
#求最少硬币数，所以需要用最大值先来初始化，float('inf')也可以用 amount + 1来替换
dp[0] = 0 #一定需要初始化
for coin in coins: #面值默认是递增的
for x in range(coin, amount + 1): #从最小面值的金额coin开始计算, 一直计算到给定的amount
dp[x] = min(dp[x], dp[x - coin] + 1)
#这里的min是为了让每种amount都取所有情况中的最少硬币数，
# 实际上是求： 对于所有的coins中的coin 求min(dp[x - coin] + 1),
return dp[amount] if dp[amount] != float('inf') else -1
''' 和上面一样，只不过遍历顺序更好理解'''
dp = [amount + 1] * (amount + 1) #硬币的面值默认最小为1时可以把float('inf')替换成amount + 1
dp[0] = 0
for i in range(1, amount + 1):
#比较好理解的遍历顺序: 为了计算每个amount（递增到给定的amount）dp值，需要遍历每一种面值的硬币
for coin in coins:
if i >= coin: #因为i(amount)是从1开始遍历而不是从最小的coin开始，所以这里要从 ”amount>最小面值“ 时开始计算才有意义，
dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[-1] == amount + 1 else dp[-1]
518. 零钱兑换 II
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# 和322以及变态跳台阶（每次可能跳1，2...n, 只不过本题变成每步可以跳指定的步数（给定的几种面值））类似
# dp[i] 来表示组成 i 块钱，需要最少的硬币数
dp = [0]*(amount+1) #临界条件也可以直接返回0
'''如果总金额为 0，那么只有一个组合情况：0'''
dp[0] = 1
for coin in coins:
for x in range(coin, amount+1):
dp[x] += dp[x-coin]
return dp[-1]
10. 正则表达式匹配
递归法时间复杂度
动态规划方法
'''
使用动态规划方法，创建模型。
该问题可以分析为使用 p的前j个字符 匹配 s的前i个字符。
s：待匹配字符
p: 匹配规则
dp[i][j]：状态数组，表示用p的前j个字符 匹配 s的前i个字符的结果
子问题分析：
p[j] == s[i] 或 p[j] == '.' ---> dp[i][j] = dp[i-1][j-1];
p[j] == '*' ---> 分两种情况
p[j-1] != s[i] ---> dp[i][j] = dp[i][j-2]
p[j-1] == s[i] ---> dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 2] or dp[i][j - 2]
解读：
# 如果*前面一个p和s匹配了, 有3种情况
# 1. 当前模式继续匹配前一个s，dp[i-1][j]
# 2. 进入下一个模式，dp[i-1][j-2]
# 3. 忽略当前模式，因为s可能会与后面的模式匹配，dp[i][j-2]
边界值分析：
当s和p最终都为空的时候，结果为true
当s和p有一个不为空的时候，结果为false -------(''与'.*'这种情况：dp[i][j]=dp[i][j-2])
注意： 二维动态规划一般dp矩阵设为：[[False] * (len(p) + 1) for _ in range(len(s) + 1)]
所以在遍历的时候原矩阵或俩字符串时：计算dp[i][j]需要判断原矩阵或俩字符串的[i-1][j-1]（当前遍历到的位置）处
'''
# @lc code=start
class Solution:
def isMatch(self, s: str, p: str) -> bool:
'''python正则表达式一行搞定'''
# return True if re.match(p+'$', s) else False #pattern后必须加上 +'$'（结束符）才行，否则只要s开头一部分和pattern匹配上了就会返回True就不会再往后考虑了
'''回溯法'''
if not p: #模式串为空时，s为空就返回True, 不为空（不可能存在匹配的情况）就返回False
return not s
first_match = bool(s) and p[0] in {s[0], '.'}
# s非空且(p[0]==s[0] or p[0]=='.'), pattern的第一个字符不能是‘*’，只能是字母或‘.’
if len(p) >= 2 and p[1] == '*':
return (self.isMatch(s, p[2:]) or
(first_match and self.isMatch(s[1:], p)) )
else:
return first_match and self.isMatch(s[1:], p[1:])
'''动态规划'''
if not p: #模式串为空时，s为空就返回True, 不为空（不可能存在匹配的情况）就返回False
return not s
# dp[i][j]表示 s 的前 i 个是否能被 p 的前 j 个匹配
# 注意初始化长度要到 len(str) + 1
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
# [0, 0] 代表空串，两空串必定匹配
dp[0][0] = True
for i in range(2, len(p) + 1):
if p[i - 1] == '*':
dp[0][i] = dp[0][i - 2] #s为空时，从pattern的第二个字符开始看，若为*可直接忽略该模式（p[0]*）
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
# 当前s == p，或p为.时匹配成功，状态为 True && dp[i-1][j-1]
if s[i - 1] == p[j - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
# 当前p为*，需要往前看
if p[j - 1] == '*':
if j - 2 >= 0:
# 如果*前面一个p和s匹配了, 有3种情况
# 1. 当前模式继续匹配前一个s，dp[i-1][j]
# 2. 进入下一个模式，dp[i-1][j-2]
# 3. 忽略当前模式，因为s可能会与后面的模式匹配，dp[i][j-2]
if p[j - 2] == s[i - 1] or p[j - 2] == '.':
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 2] or dp[i][j - 2]
# 没有匹配，需要看是不是忽略*这个模式的情况
else:
dp[i][j] = dp[i][j - 2]
return dp[-1][-1]
''' 去掉注释的动态规划简洁形式'''
ls, lp = len(s), len(p)
dp = [[False for _ in range(lp + 1)] for _ in range(ls + 1)]
dp[0][0] = True
for j in range(2, lp + 1):
dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
for i in range(1, ls + 1):
for j in range(1, lp + 1):
m, n = i - 1, j - 1 ###当前遍历访问到 s的i-1(m) 和 p的j-1(n) 处, 先统一好防止混淆
if p[n] == '*':
if s[m] == p[n - 1] or p[n - 1] == '.':
dp[i][j] = dp[i][j - 2] or dp[i - 1][j]
else: dp[i][j] = dp[i][j - 2]
elif s[m] == p[n] or p[n] == '.':
dp[i][j] = dp[i - 1][j - 1]
return dp[-1][-1]
139. 单词拆分
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
'''动态规划： 区间匹配（start:end, 双指针）'''
n = len(s)
dp = [False]*(n+1) #dp[i]表示s的前i位是否可以用wordDict中的单词表示
dp[0] = True #######空字符s可以被表示
for i in range(n): #对于每个位置考虑不同长度i:j是否在wordDict中
for j in range(i+1, n+1):
if dp[i] and (s[i:j] in wordDict):
dp[j] = True
return dp[-1]
'''记忆化回溯'''
import functools
@functools.lru_cache(None)
def back_track(s):
if(not s):
return True
res=False
for i in range(1,len(s)+1):
if(s[:i] in wordDict): #匹配上一个单词后就从此处往后继续匹配
res=back_track(s[i:]) or res
return res
return back_track(s)
'''
functools.lru_cache(maxsize=128, typed=False)
这个装饰器实现了备忘的功能，是一项优化技术，把耗时的函数的结果保存起来，避免传入相同的参数时重复计算。
lru 是（least recently used）的缩写，即最近最少使用原则。表明缓存不会无限制增长，一段时间不用的缓存条目会被扔掉。
这个装饰器支持传入参数,:
maxsize : 是保存最近多少个调用的结果，最好设置为 2 的倍数，默认为 128。如果设置为 None 的话就相当于是 maxsize 为正无穷了。
type : 如果 type 设置为 true，即把不同参数类型得到的结果分开保存，如 f(3) 和 f(3.0) 会被区分开。
有了缓存之后，追踪次数会明显减少，不会调用递归。
140. 单词拆分 II
112. 路径总和
112. 路径总和
112. 路径总和
112. 路径总和
112. 路径总和
112. 路径总和
112. 路径总和
