这里用的例子是109. Triangle
一个标准的DFS答案是这么写的:
class Solution:
"""
@param triangle: a list of lists of integers
@return: An integer, minimum path sum
"""
def minimumTotal(self, triangle):
# corner case
if not triangle:
return 0
# pass common data (read only) to workspace
self.T = triangle
# find answer in the last row
i = len(self.T) - 1
ans = []
for j in range(len(self.T[i])):
ans.append(self.dp(i, j))
# return min of ans
return min(ans)
def dp(self, i, j):
# if first row, no need to trace back
if i == 0:
return self.T[i][j]
# init for min comparison
path_sum = float("inf")
# update answer for left parent path
if j - 1 >= 0:
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j-1)])
# update answer for right parent path
if j < len(self.T[i-1]):
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j)])
return path_sum
当然是妥妥的TLE
于是我们可以用一个Dict保存答案,如果算过就直接调答案,如果没算过再算。
class Solution:
"""
@param triangle: a list of lists of integers
@return: An integer, minimum path sum
"""
def minimumTotal(self, triangle):
# corner case
if not triangle:
return 0
# pass common data (read only) to workspace
self.T = triangle
# find answer in the last row
i = len(self.T) - 1
ans = []
for j in range(len(self.T[i])):
ans.append(self.dp(i, j))
# return min of ans
return min(ans)
def __init__(self):
self.dp_data = dict()
def dp_fun(self, i, j):
# if first row, no need to trace back
if i == 0:
return self.T[i][j]
# init for min comparison
path_sum = float("inf")
# update answer for left parent path
if j - 1 >= 0:
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j-1)])
# update answer for right parent path
if j < len(self.T[i-1]):
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j)])
return path_sum
def dp(self, i, j):
"""
path sum to T[i][j]
"""
if (i, j) not in self.dp_data:
self.dp_data[(i, j)] = self.dp_fun(i, j)
return self.dp_data[(i, j)]
另外还有一个decorator叫lru_cache实现了完全相同的功能。只不过它用的不是dict而是ordered dict。
from functools import lru_cache
class Solution:
"""
@param triangle: a list of lists of integers
@return: An integer, minimum path sum
"""
def minimumTotal(self, triangle):
# corner case
if not triangle:
return 0
# pass common data (read only) to workspace
self.T = triangle
# find answer in the last row
i = len(self.T) - 1
ans = []
for j in range(len(self.T[i])):
ans.append(self.dp(i, j))
# return min of ans
return min(ans)
@lru_cache(None)
def dp(self, i, j):
# if first row, no need to trace back
if i == 0:
return self.T[i][j]
# init for min comparison
path_sum = float("inf")
# update answer for left parent path
if j - 1 >= 0:
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j-1)])
# update answer for right parent path
if j < len(self.T[i-1]):
path_sum = min([path_sum, self.T[i][j] + self.dp(i-1, j)])
return path_sum
就是记得先import。