class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
s=[0]*(len(triangle)+1)
for i in range(len(triangle)-1,-1,-1):
for j in range(i+1):
s[j]=min(s[j],s[j+1])+triangle[i][j]
return s[0]
注意
1.s初始化n+1，各个边界条件要注意
2.i从n-1开始，由于s初始化为0，所以是s[j]初始化为a[i,j],不用写特殊处理代码
3.range(start,stop[,step])，左闭右开
4.自底向上的动态规划
重做,15分钟一次通过，爽啊：
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
tmp=[0]*(len(triangle[len(triangle)-1])+1) # zh这个可以更简洁
for i in reversed(triangle):
for j,n in enumerate(i):
tmp[j]=min(tmp[j],tmp[j+1])+n
return tmp[0]
注意
1.reversed,反向迭代
2.enumerate ，既有数字也有序号
使用迭代，增加备忘录存储子问题，每次使用这个方法的时候总会忘记存储备忘录，也忘记记录备忘录，等提交不通过才进行改正
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
mem=[[-1]*(i+1) for i in range(len(triangle))]
return self.dp(0,0,triangle,mem)
def dp(self,i:int,j:int,triangle:List[List[int]],mem:List[List[int]]) ->int:
if i==len(triangle)-1:
mem[i][j]=triangle[i][j]
return mem[i][j]
# 忘了从备忘录读取了，又光顾着取，忘了存了
if(mem[i][j]!=-1):return mem[i][j]
mem[i][j]=min(self.dp(i+1,j,triangle,mem),self.dp(i+1,j+1,triangle,mem))+triangle[i][j]
return mem[i][j]
注意
1.三角矩阵的生成方式
2.备忘录的存储和读取
