数据结构极客视频6 动态规划
数据结构极客视频6—动态规划
动态规划
动态规划题目 leetcode70 跳台阶
class Solution:
def climbStairs(self, n: int) -> int:
if n<=2:
return n
fnPre=2
fnPrePre=1
re=0
for i in range(3,n+1):
re=fnPre+fnPrePre
fnPrePre,fnPre=fnPre,re
return re
###################华丽的分割线##################
if n<=2:
return n
re={}
re[1]=1
re[2]=2
for i in range(3,n+1):
re[i]=re[i-1]+re[i-2]
return re[n]
DP题目 120
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle:return 0
re=triangle[-1]
for row in range(len(triangle)-2,-1,-1):
for col in range(len(triangle[row])):
re[col]=triangle[row][col]+min(re[col],re[col+1])
return re[0]
题目 乘积最大子序列
定义状态:对于当前的每一位:与前面的相乘是最大 或者自己是最大 但是可能当前是负数 那么和前面的负数相乘就是最大 三个比较就好了 当然也需要保存最小值 后面可能继续用
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# re=[]
# dp=[[0 for i in range(2)] for j in range(2)]
# dp[0][0],dp[0][1],re=nums[0],nums[0],nums[0]
# for i in range(1,len(nums)):
# x,y=i%2,(i-1)%2
# dp[x][0]=max(dp[y][0]*nums[i],dp[y][1]*nums[i],nums[i])
# dp[x][1]=min(dp[y][0]*nums[i],dp[y][1]*nums[i],nums[i])
# re=max(dp[x][0],re)
# return re
if not nums: return
curMax,curMin,re=nums[0],nums[0],nums[0]
for i in range(1,len(nums)):
curMax=curMax*nums[i]
curMin=curMin*nums[i]
curMax,curMin=max(curMax,curMin,nums[i]),min(curMin,curMax,nums[i])
re = curMax if curMax>re else re
return re