二道常考动态规划题目

读前福利，送大家一些电子书

跳台阶问题

70. 爬楼梯

问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

示例：

输入：2

返回值：2

说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2。

分析问题

拿到这个问题，我们可以反过来思考，要想爬到n级台阶，我们只能从n-1级跳1级或者从n-2级跳2级两种可能。我们用f(x)来表示爬到x级台阶的方案数，那么可以得出f(x)=f(x-1)+f(x-2)。有了递推公式，我们就可以采用动态规划的方法来解决问题了。

class Solution():
    def climbStairs(self,n):
        if n==0 or n==1:
           return 1
        dp=[]
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

我们可以看到该算法的时间复杂度是O(n)，空间复杂度也是O(n)。由于爬到n级台阶的跳法只是依赖于n-1级和n-2级的跳法，所以我们不需要保存之前每一级台阶的跳法数。最需要保存它前两个台阶的跳法数就好。

class Solution():
    def climbStairs(self,n):
        if n==0 or n==1:
            return 1
        p=0
        q=0
        r=1
        for i in range(1,n+1):
            p=q
            q=r
            r = p + q
        return r

我们可以看到该算法的时间复杂度是O(n)，空间复杂度是O(1)。

连续子数组的最大和

LeetCode 53. 最大子数组和

问题描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

示例：

输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

分析问题

因为题目是求所有子数组的和的最大值，我们可以假设以第i个数结尾的连续子数组和的最大的值为f(i)。现在我们只需要求出所有的f(i)，拿出其中最大的就是题目的解。

我们下面来看一下如何求解f(i)。对于以第i个数结尾的子数组来说，f(i)要么等于nums[i]，要么等于f(i-1)+nums[i]，这取决于nums[i]和f(i-1)+nums[i]的大小。即f(i)=max(nums[i],f(i-1)+nums[i])。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if array is None or len(array)==0:
           return 0
        n=len(array)
        dp=[0]*n
        dp[0]=array[0]
        for i in range(1,n):
            dp[i]=max(array[i],dp[i-1]+array[i])
        return max(dp)

我们可以看到这里的时间复杂度和空间复杂度都是O(n)。由于我们在求解f(i)的时候，只和f(i-1)和nums[i]有关，而和f(i-2)、f(i-3)…无关，所以，我们只需要一个变量去保存f(i-1)就好了，这样可以把空间复杂度减低为O(1)。下面我们来看一下代码如何实现。

def maxSubArray(array):
    if array is None or len(array)==0:
        return 0
    n=len(array)
    pre=array[0]
    result=array[0]
    for i in range(1,n):
        pre=max(array[i],pre+array[i])
        result=max(result,pre)
    return result