数据结构算法刷题（29）动态规划

 思路一：回溯：按照选和不选的判断方式，使用回溯来解决这个问题。

class Solution:

    def rob(self, nums: List[int]) -> int:

        n = len(nums) #数组的长度

        def dfs(i):

            if i<0: #到达边界条件后

                return 0 #返回最大金额是0

            res = max(dfs(i-1),dfs(i-2)+nums[i]) #如果选，下一次递归的就是i-2，并且要加上nums[i]的值，如果不选，下一次递归i-1。比较选或者不选的最大值并返回。

            return res

        res = dfs(n-1) #传入的是数组的最大下标

        return res

问题：回溯使用递归，时间复杂度是指数级别的，会超时，那如何让时间降下来？

思路二：有两次相同的计算结果，那就把每个位置的计算结果保存下来，可以把时间缩短。

 

class Solution:

    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        cache = [-1]*n #因为每个位置一定不是负数

        def dfs(i):

            if i<0:

                return 0

            if cache[i] != -1: #当前的位置不是-1，那么这个位置被计算过，直接返回计算的结果

                return cache[i] 

            res = max(dfs(i-1),dfs(i-2)+nums[i])

            cache[i] = res #把当前位置的计算结果保存

            return res

        res = dfs(n-1)

        return res

问题：这种方式的空间复杂度就是O(n)，如何将空间复杂度降下来：递推

思路三：我们可以确定的知道每个节点是那几个数归的结果，那把递的过程省略，直接归，也就是从下往上计算结果。

 

 循环对数组下标有要求，所以下标从2开始。

class Solution:

    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        f = [0]*(n+2) #归的数组长度是n+2，每个数组的值是0

        for i,x in enumerate(nums): #遍历nums

            f[i+2] = max(f[i+1],f[i]+x) # 等同于res = max(dfs(i-1),dfs(i-2)+nums[i])

        return f[n+1]

改进空间复杂度：

class Solution:

    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        f0 = f1 = 0

        for i,x in enumerate(nums):

            new_f = max(f1,f0+x)

            f0 = f1

            f1 = new_f

        return f1

思路：

class Solution:

    def climbStairs(self, n: int) -> int:

        dp0 = 1

        dp1 = 1

        if n <= 1:

            return 1

        dp = 0

        for i in range(2,n+1):

            dp = dp0 + dp1

            dp0 = dp1

            dp1 = dp

        return dp

 思路：

 

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        n = len(cost)

        dp0 = 0 #第0级台阶的顶部最小花费是0

        dp1 = min(cost[0],cost[1]) #第1级台阶的顶部台阶的最小花费是cost[0]或cost[1]的最小值

        for i in range(2,n):

            dp = min(dp1+cost[i],dp0+cost[i-1])

            dp0 = dp1

            dp1 = dp

        return dp1