leetcode刷题之路

更新中。。。。
动态规划(Dynamic Programming)四要点:

  • 递推
  • 状态的定义:opt[n], dp[n], fib[n]{opt[n],\ dp[n], \ fib[n]}
  • 状态转移方程:opt[n]=best_of(opt[n1], opt[n2], ...){opt[n]=best\_of (opt[n-1], \ opt[n-2],\ ...)}
  • 最优子结构

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

class Solution:
    def climbStairs(self, n: int) -> int:
        # 动态规划
        # DP状态的定义:f(n)表示到第n阶的总走法个数
        # DP状态转移方程:f(n) = f(n-1) + f(n-2)表示走一阶或走二阶上楼梯
        
        # 斐波那契数列求和
        x, y = 1, 1
        for _ in range(1,n):
            x, y = y, x + y
        return y

内存消耗为O(1),时间复杂度为O(N)。
执行用时 : 48 ms, 在Climbing Stairs的Python3提交中击败了80.81% 的用户
内存消耗 : 13.2 MB, 在Climbing Stairs的Python3提交中击败了35.74% 的用户

斐波那契数列的最优时间复杂度为O(logN)。所以上面的代码还可以再优化。

120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上
leetcode解题:动态规划(下)
说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        """
        三角型二维数组:m*n
        DP状态定义:dp[i, j]指从下面一层走到当前层,路径和的最小值
        DP状态方程:dp[i, j] = min(dp(i+1, j), dp(i+1, j+1)) + triangle[i, j]
        DP初始状态: dp[m-1, j] = Triangle[m-1, j]
          注意这里比较的不是数组元素值,而是路径和
          最后一直递推到dp[0, 0]就是我们要的值了
        
        """
        if not triangle:
            return 0
        
        # res指三角形最下面的一层,既是triangle数组里的元素,又是当前的最小路径
        res = triangle[-1]
        
        # 状态转移是从倒数第二行开始的(也就是递推的顺序)
        for i in range(len(triangle)-2, -1, -1): 
            for j in range(len(triangle[i])):
                res[j] = min(res[j], res[j+1]) + triangle[i][j]
                # 上面这一行代码用到了状态压缩的思路,其实就是数组复用而已,因为数组元素用过一次后就用不着了,接着被状态值覆盖掉,这一可以省去不少空间。
        return res[0]

执行用时 : 68 ms, 在Triangle的Python3提交中击败了49.63% 的用户
内存消耗 : 13.3 MB, 在Triangle的Python3提交中击败了100.00% 的用户

152. 乘积最大子序列

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
示例:

输入: [2, 3, -2, 4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6========================================
输入: [-2, 0, -1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
========================================
输入: [2, 3 , -10, 5, -1]
输出: 300
解释: 负负得正,结果就是全数组的乘积。

股票买卖系列【121、122、123、309、188、714】

300. 最长上升子序列

322. 零钱兑换

72. 编辑距离

;