Leetcode-动态规划

发布时间：2020-12-14 05:09:49 所属栏目：大数据来源：网络整理

导读：70. 爬楼梯?https://leetcode-cn.com/problems/climbing-stairs/ 假设你正在爬楼梯。需要? n ?阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定? n ?是一个正整数。解：暴力，如果只有一阶，就只有一种方

70. 爬楼梯?https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要?n?阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定?n?是一个正整数。

解：

暴力，如果只有一阶，就只有一种方法；如果只有二阶，就只有两种方法。那么n阶的方法数就等于n-1阶和n-2阶方法数之和。但直接递归，有太多重复计算，超时。O(2ⁿ)

class Solution:
    def climbStairs(self,n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n-1) + self.climbStairs(n-2)

递归+记忆化，放数组里缓存。把每一步的结果存储在?

class Solution:
    def climbStairs(self,n: int) -> int:
        memo = [0]*(n+1)  # memo[i]表示从第i阶到第n阶的方法数，出发点是第0阶
        
        def helper(i,n,memo):  # 起始点i，终点n
            if i > n:  # 越界，最高起点直接在第n阶
                return 0
            if i == n:   # 不用动，一种方法
                return 1
            
            if memo[i] > 0:
                return memo[i]  # 如果已经算过了，就不用再算了
            
            memo[i] = helper(i+1,memo) + helper(i+2,memo)
            
            return memo[i]
            
        return helper(0,memo)

动态规划，递推，?f(n) = f(n-1) + f(n-2) ，f(1)=1,f(2)=2。O(N)? 其实也可以不用开一个数组。

class Solution:
    def climbStairs(self,n: int) -> int:
        if n <= 2:
            return n
        
        f = [0]*n
        f[0],f[1] = 1,2
        for i in range(2,n):
            f[i] = f[i-1]+ f[i-2]
        return f[n-1]

# O(1) 空间
class Solution:
    def climbStairs(self,n: int) -> int:
        if n <= 2:
            return n
        
        pre1 = 1
        pre2 = 2
        for i in range(2,n):
            cur = pre1 + pre2
            
            pre1 = pre2
            pre2 = cur
            
        return cur

Binets 矩阵乘法

特征根

120.三角形最小路径和?https://leetcode-cn.com/problems/triangle/

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

说明：

如果你可以只使用?O(n)?的额外空间（n?为三角形的总行数）来解决这个问题，那么你的算法会很加分。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!