动态规划问题

1 最大子序和问题（入门）

• 题目：

  给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 解决代码：

  class Solution(object):
      def maxSubArray(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          if len(nums)==1:
              return nums[0]
          maxu = nums[0]
          pre = nums[0]
          for num in nums[1:]:
              # print(num)
              pre = max(num+pre,num)
              maxu = max(pre,maxu)
          return maxu

• 题解：

  这道题是经典的动态规划问题了，虽然我的代码还是有很多的冗余，但是基本上就是这个思想。简单来说要求最大子序和，分解为子问题就是求以 nums数组中每一个元素为结尾的最大子序和是什么。定义表示 nums第项结尾的最大子序列和是多少，而这一子问题表示为：

  
  也就是说要么是先前最大子序列和加上第项元素，或者由于已经小于 0，因此 nums[i]项反而相较之下更大，取两者之间最大的一个值。

  如何理解，不加上这一项的前项是我们最终要求的最大子序列和呢？问题在于我们定义的一定包括第项，最后在求整个数组的最大子序列和的时候需要便利数组，找到最大值，也可以和我上述代码一样用 pre来记录上一轮的，这样就不用再做数组了，空间复杂度可以降到。

2 爬楼梯问题（简单）

• 题目：

  给你一个整数数组 cost，其中 cost[i]是从楼梯第 i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

  你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

  请你计算并返回达到楼梯顶部的最低花费。

• 解决代码：

  class Solution(object):
      def minCostClimbingStairs(self, cost):
          """
          :type cost: List[int]
          :rtype: int
          """
          n=len(cost)
          dp=[0]*(n+1)
          for i in range(2,n+1):  #range左包右不包
              dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
          return dp[n]

• 题解：

  这道问题也是一道典型的动态规划，感觉思考这一类问题要反向思考，即要跳到最后一级台阶的前一步要跳到哪个台阶。设要跳到第个台阶，那么一共就只有两种可能，要么从第级台阶花费 cost[i-1]元跳过来，要么从级台阶花费 cost[i-2]元跳过来。也就是说问题可以进行转换，设为跳到第级台阶需要花费的钱，共 n 级台阶，起跳为下标为 0 或下标为 1 处，则可以列出公式：