这三题解题思路相同，也是我个人比较喜欢的动态规划题。
leetcode746：
cost = [10,15,20]
创建一个二维数组如下：
dp = [[0,0],[0,0],[0,0],[0,0]]
赋值:
dp = [[0,0],[0,10],[10,15],[15,10+20]]
最后reture min[15,10+20]
思路:
dp[k][0]代表第k个阶梯不走，dp[k][1]代表第k个阶梯走
dp[k][0] = dp[k-1][1]
dp[k][1] = min(dp[k-1][0]+cost[k],dp[k-1][1]+cost[k])
代码：
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:if cost == []:return 0if len(cost)<3:return min(cost)dp = [[0,0] for _ in range(len(cost)+1)]dp[1] = [0,cost[0]]for i in range(1,len(cost)):dp[i+1] = [dp[i][1],min(dp[i])+cost[i]]return min(dp[-1])
同理leetcode198
class Solution:def rob(self, nums: List[int]) -> int:if len(nums)<3 and len(nums)>0:return max(nums)if len(nums) ==0:return 0sumlist = [0,nums[0]]for i in range(1,len(nums)):sumlist.append(max((sumlist[-2]+nums[i]),sumlist[-1]))return sumlist[-1]
剑指offer42题解为：
class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums) == 0:return 0if len(nums) == 1:return nums[0]neinf = float('-inf')dp= [[0,0] for _ in range(len(nums))]dp[0] = [neinf,nums[0]]for i in range(1,len(nums)):dp[i] = [max(dp[i-1][0],dp[i-1][1]),nums[i]+max(0,dp[i-1][1])]return max(max(row) for row in dp)