首页 > 其他分享 >力扣-动态规划全解

力扣-动态规划全解

时间：2024-07-22 12:08:18浏览次数：9  
标签：int max len 力扣 range prices 全解 动态 dp

目录

动态规划

  • 基础类题目：斐波那契数列、爬楼梯
  • 背包问题
  • 打家劫舍，最后一道树形 DP
  • 股票问题
  • 子序列问题，编辑距离

注意：dp 数组的定义和下标的含义 & 递推公式 & dp 数组如何初始化 & 遍历顺序 & 打印 dp 数组

斐波那契数列-EASY

分析：

斐波那契数列 1 1 2 3 5 8

  1. 确定 dp 数组的含义：dp[i], 下标 i, 第 i 个斐波那契数的值为 dp[i]
  2. 确定递推公式：dp[i] = dp[i-1] + dp[i-2]
  3. dp 数组如何初始化：dp[0] = 1, dp[1] = 1
  4. 确定遍历顺序：从前向后遍历
  5. 打印 dp 数组

代码

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

问题：n=45时答案错误

  • 当n的值非常大时，使用列表来存储所有的斐波那契数可能会导致内存使用问题。
  • 如果只需要最后一个斐波那契数（即dp[n]），则不需要存储整个序列。

优化代码

class Solution:
    def fib(self, n: int) -> int:
        if n <=1:
            return n
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, a+b
        return b

还是在 n=45 时出错

大整数溢出

可以使用取模运算来避免整数过大，如在计算斐波那契数时使用% 1000000007。

class Solution:
    def fib(self, n: int) -> int:
        if n <=1:
            return n
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, (a+b) % 1000000007
        return b

时间复杂度logn的算法

爬楼梯-EASY

image-20240722114606879

代码

class Solution:
    def climbStairs(self, n: int) -> int:
        # 定义 dp 数组
        dp = [0 for _ in range(n+1)]
        # dp[i] 表示 到达第 i 阶有多少种不同的方法
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            dp[i]  =dp[i-1] + dp[i-2]
        return dp[n]

思考

为什么爬楼梯不需要防止大整数溢出?

斐波那契数列的一个关键性质是它的项数随着指数增长，但是其值却以非常快的速率增长，很快就会超过大多数编程语言能够表示的整数范围。然而，对于爬楼梯问题，到达第 n 阶楼梯的方法数实际上总是一个正整数，并且这个数总是小于或等于 \(2^{n}\)。这是因为在最坏的情况下，每一步都只走 1 阶，这样就有 \(n\)种 方法；而每一步都走 2 阶，则最多有 \(\frac{n}{2} + \frac{n}{2}\)种方法，这在数值上不会超过 \(2^{n}\)。

使用最小花费爬楼梯-EASY

image-20240722114634907

到达不花费，向上跳才花费。

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        min_cost = math.inf
        # 阶梯的层数 
        n = len(cost)
        # dp数组 dp[i]表示到达第i层的最低花费
        dp = [math.inf for _ in range(n+2)]
        # 顶楼为 n+1
        dp[0], dp[1] = 0, 0
        for i in range(2, n+1):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        return dp[n]

不同路径-Middle

image-20240722114652105

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 每次向下或向右一步
        # 定义二维 dp 数组
        # di[i][j]表示到达(i, j)的不同路径数
        dp = [[0 for _ in range(n)] for _ in range(m)]

        # 如果 i<m-1, 可以向下走
        # 如果 j<n-1，可以向右走

        # dp 数组初始化
        # 第一行，全为 1
        # 第一列，全为 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(m):
            dp[i][0] = 1
        # 遍历
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[m-1][n-1]

深搜代码 & 超时

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def dfs(i, j):
            if i > m or j > n:  # 越界了
                return 0
            if i == m and j == n:  # 找到一种方法
                return 1
            return dfs(i + 1, j) + dfs(i, j + 1)
        
        return dfs(1, 1)

不同路径II-Middle

image-20240722114718419

代码

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 每次向下或者向后，到右下角
        # 网格中有障碍物，障碍物网格
        # 定义 dp 数组，二维
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # dp数组初始化
        # 障碍物处为 0
        # 第一行如果有障碍物，则右侧均为 0
        # 第一列如果有障碍物，则下方均为 0
        obs_flag = False
        for j in range(n):
            if obstacleGrid[0][j] == 0 and not obs_flag:
                dp[0][j] = 1
            if obstacleGrid[0][j] == 1:
                obs_flag = True
            if obs_flag:
                dp[0][j] = 0
        obs_flag = False
        for i in range(m):
            if obstacleGrid[i][0] == 0 and not obs_flag:
                dp[i][0] = 1
            if obstacleGrid[i][0] == 1:
                obs_flag = True
            if obs_flag:
                dp[i][0] = 0
        # 遍历
        # 如果当前位置上方有障碍，只能从左侧过来
        # 如果当前位置左侧有障碍，只能从右侧过来
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
        return dp[m-1][n-1]

不同路径 III-HARD

image-20240722114733596

回溯代码 & 四个方向 & 路径数

class Solution:
    def uniquePathsIII(self, grid:List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(x:int, y:int, left:int) -> int:
            if x<0 or x>=m or y<0 or y>=n or grid[x][y]<0:
                return 0 # 不合法
            # 到达终点时必须要访问所有的无障碍方格
            if grid[x][y] == 2:
                return left == 0
            # 标记为已访问过
            grid[x][y] = -1
            # 对当前位置的上下左右四个方向进行递归搜索，并计算路径数。
            ans = dfs(x-1, y, left-1) + dfs(x, y-1, left-1) + dfs(x+1, y, left-1) + dfs(x, y+1, left-1)
            # 恢复现场
            grid[x][y] = 0
            return ans
        
        cnt0 = sum(row.count(0) for row in grid)
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v == 1:
                    return dfs(i, j, cnt0+1)

整数拆分-MID*

image-20240722114751895

代码

class Solution:
    def integerBreak(self, n: int) -> int:
        # 拆分为 k 个正整数的和，且乘积最大化
        # 返回最大乘积
        # 定义 dp 数组，dp 数组的含义
        # dp[i] 将 i 拆分为 k 个正整数且乘积最大化
        dp = [0]*(n+1)
        dp[0] = 0
        dp[1] = 0
        dp[2] = 1
        for i in range(3, n+1):
            for j in range(1, int(i/2)+1):
                dp[i] = max(dp[i], j * dp[i-j], j*(i-j))
        print(dp)
        return dp[n]

思考

  1. 对于所求 dp[i]，及要拆分的正整数 i
  2. 将 i 拆分为 j 和 i-j，此时有两种方案
    1. i-j 不再拆分
    2. i-j 再次进行拆分，拆分之后的乘积依赖于dp[i-j]

不同的二叉搜索树-MID

image-20240722114814500

代码

class Solution:
    def numTrees(self, n: int) -> int:
        # 整数 n
        # n 个节点，1-n
        # 互不相同的二叉搜索树
        # 类似整数拆分
        # 11 个节点，左边 5 个，右边 5 个；左边 4 个，右边 6 个；
        # n = 0, 0
        # n = 1, 1 种
        # n = 2, 2 种
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1
        if n <=1:
            return n
        dp[2] = 2
        for i in range(3, n+1):
            for j in range(0, i):
                # i个节点，i-1 在子树，拆分为j和i-1-j
                dp[i] += dp[j] * dp[i-1-j]
        return dp[n]

思考

  1. 对 i 进行拆分，根节点占用一个值，实际拆分的是 i-1
  2. 拆分为 j 和 i-1-j，左侧 j 个依赖于dp[j]，右侧 i-1-j 个，依赖于 dp[i-1-j]
  3. 总的种数为左右两侧相乘
  4. dp 数组输出化时，dp[0] = 1，0 个节点组成的二叉树不存在，但左侧子树 0 个节点时，算作一种，且需要与右侧种数相乘，故为 1

背包问题-理论基础

01 背包：n 种物品每种物品只有一个。

完全背包：n 种物品每种物品无限个。

多重背包：n 种物品每种物品个数各不相同。

01 背包问题

image-20240722114918463

回溯算法暴力搜索

每个物品两种状态，取 & 不取。

二维 dp 数组解法

dp 数组的含义：[0, i]物品任取放入容量为 j 的背包

递推公式，对于 \(dp[i, j]\) 及物品 i：存在两种状态

  1. 不放物品 i：依赖于\(dp[i-1, j]\)
  2. 放物品 i：依赖于 \(dp[i-1, j-w[i]] + v[i]\)

dp数组初始化：行为物品，列为容量

  • 第一行初始化，物品 0，如果容量大于物品 0 的容量，最大价值为物品 0 的价值，否则价值为 0.
  • 第一列初始化，容量 0，如果物品小于容量 0，则价值为物品的价值，否则价值为 0.

遍历顺序：在这里二维 dp 数组先遍历物品再遍历背包或者先遍历背包再遍历物品都可以。

二维 dp 数组降至一维 dp 数组 & 滚动数组

每一行依赖于上一行的结果，将上一层数据拷贝下来。

dp 数组定义：dp[j] 表示容量为 j 的背包所能装下的最大价值为 dp[j]

递推公式：还是根据物品 i 来考虑的

  1. 不放物品 i：就是 dp[j]
  2. 放物品 i：\(dp[j-weight[i]] + value[i]\)

dp 数组的初始化：

  • dp[0] = 0
  • 非 0 下标时，也要初始化为 0，因为递推公式要对两个价值取最大值，这里应该初始化为一个小的值。

遍历顺序：先遍历物品，再遍历背包，且背包倒序遍历，防止物品重复放入。

面试题目

  1. 01 背包问题，用二维dp数组实现，两个 for 循环能不能颠倒
  2. 再用 1 维 dp 数组实现，两个 for 循环可不可以颠倒顺序，容量 for 循环为什么从后向前遍历，二维 dp 数组中为什么不用从后向前遍历
    1. 1 维 dp 数组是重复利用的

分割等和子集-EASY

image-20240722114935107

一维 dp 数组 代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 等分为两部分
        if sum(nums) % 2 != 0:
            return False
        target = sum(nums) // 2
        # 定义一维 dp 数组
        # 含义：dp[i] 容量为 i 能够容纳的最大价值
        dp = [0] * (target+1)
        # 初始化，dp[0] = 0，非 0 时也为 0，后续有 max 操作
        
        # 主要这里对物品进行遍历
        for num in nums:
            # 对从0-target的所有容量进行遍历
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j-num] + num)
        return dp[target] == target

思路

  • 抽象为 01 背包问题
  • 背包容量是从 0 开始的

二维 dp 数组 代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False
        target = sum(nums) // 2
        dp = [[False for _ in range(target + 1)] for _ in range(len(nums)+1)]
        # 初始化第一列
        for i in range(len(nums)+1):
            dp[i][0] = True
        for i in range(1, len(nums)+1):
            for j in range(1, target+1):
                if j < nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]

        return dp[len(nums)][target]

最后一块石头的重量 II-MID

image-20240722114950856

思考

  1. 回溯暴力应该可以做
  2. 背包问题
    1. 两两石头块进行粉碎，求最终的最小值，也可以转化为分成两堆，其和尽量接近，这样相减得到的值最小。

一维 dp 数组代码

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 同样分成两堆，要求尽可能接近，这样碰撞的差值最小
        target = sum(stones) // 2

        # 定义一维 dp 数组
        dp = [0] * (target+1)
        # 含义 容量为 0 的背包，能装的最大价值
        # 初始化

        # 遍历顺序
        for i in range(len(stones)):
            # 内层循环保证了容量 j 都比 stone[i]要大
            for j in range(target, stones[i]-1, -1):
                dp[j] = max(dp[j], stones[i] + dp[j - stones[i]])
        return sum(stones) - dp[target]*2

目标和-MID *

image-20240722115015675

思路

  • 对于每一个元素，要么加要么减，类似于要么选，要么不选，所以回溯暴力算法应该可以解。
  • 加和减也可以看做两个集合，（分割等和子集是两个集合相等，最后一块石头的重量是两个集合尽可能接近），这道题要求两个集合的总和为指定的 target。
  • 给定的 nums 为非负整数数组，可以拆分为两个集合，两个集合相减最终得到的值为 target。

如果一个集合，被减数为 A

\(A - (sum-A) = target, A-sum + A = target\)

\(A = \frac{sum + target}{2}\)

故 \(sum + target\)一定能够整除 2.

dp 数组含义：dp[j] 表示容量为 j 的背包得到价值为 add 有 dp[j]种方法，总的方法为 dp[0] + dp[1] + … + dp[j]

问题就是在集合nums中找出和为 add 的组合。

确定递推公式

  • 要求 dp[j]，如果加入 nums[i]，则取决于dp[j - nums[i]]
  • image-20240722115035916
  • 类似的组合问题 dp[j] += dp[j - nums[i]]

一维 dp 数组代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 题目拆解：运算结果等于 target == 背包容量为 target 时，容纳的最大价值为 target
        # 每个元素两种状态，加或减
        # 加集合，减集合
        # 要求加集合 - 减集合 = target
        # 问题抽象：加集合，背包问题，容量为加集合的背包所能容纳的物品价值恰好等于容量，且减去减集合后为 target
        # 加集合 = add
        if sum(nums) < abs(target):
            return 0
        add = (sum(nums) + target) // 2
        if (sum(nums) + target) % 2 != 0:
            return 0
        # 定义 dp 数组
        dp = [0] * (add + 1)
        # dp数组初始化
        # 背包容量为 0，装满背包有 1 中方法
        dp[0] = 1

        # 考虑物品 num
        for num in nums:
            for j in range(add, num-1, -1):
                dp[j] += dp[j-num]
        return dp[add]

二维 dp 数组代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        if total_sum < abs(target):
            return 0
        if (target + total_sum) % 2 != 0:
            return 0
        # 目标和
        target_sum = (target + total_sum) // 2
        #创建二维 dp 数组，行表示选取的元素数量，列表示累加和
        dp = [[ 0 for _ in range(target_sum + 1)] for _ in range(len(nums)+1)]
        # 初始化：0 个物品装满容量为 0的背包，方法有一种
        dp[0][0] = 1

        # 遍历
        for i in range(1, len(nums)+1):
            # 容量从 0-target_sum
            for j in range(target_sum+1):
                # 不选取当前物品
                dp[i][j] = dp[i-1][j]
                if j >= nums[i-1]:
                    # 选当前物品
                    dp[i][j] += dp[i-1][j - nums[i-1]]
        return dp[len(nums)][target_sum]
  • 当前元素为 \(nums[i]\)，上一个元素为 \(nums[i-1]\)
    • 不选取当前物品时 ✅
    • 选取当前物品：如果当前容量为 j，要考虑当前容量是否大于上一个元素 \(nums[i-1]\)，如果大于则 \(dp[i][j]\) 可以依赖于 \(dp[i-1][j-nums[j-1]]\)
    • +=

一和零-MID*

image-20240722115054956

子集需要满足：最多 m 个 0 ，最多 n 个 1

求：这样的子集最多有多少个元素

思路

m个 0，n 个 1 的容器，装满这个容器，最多有多少个元素。

容器==背包，两个维度的背包，之前的背包只有一个容量的维度，现在相当于是一个容量装 0，一个容量装 1，两个维度。

装满这个背包最多有多少个物品。

零一背包，每个物品只能使用一次。

3 个变量，m，n，最多多少个物品。

每个物品的重量其实就是每个字符串包含 x 个 0 和 y 个 1.

定义二维 dp 数组

\(dp[i][j]\) 定义为 m=i，n=j 的背包最多装多少个物品。

递推公式

当前物品的重量：x 个 0，y 个 1

选中当前物品之后，数量要+1

\(当前物品 重量(Num_0, Num_1) = (x, y)\)

\(dp[i-x][j-j] + 1\)

二维 dp 数组代码

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 二进制字符串数组
        # 最大子集长度
        # 最大子集最多包含 m 个 0，n 个 1
        
        # 该子集看做一个背包，两个维度的背包 m 和 n
        # 定义二维 dp 数组
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        # 含义 dp[i][j]
        # m = i,n = j 的背包，最多装的物品数为 dp[i][j]
        # 初始化
        dp[0][0] = 0
        # 物品个数
        num  = len(strs)
        # 0维度重量
        weight_0 = [0] * num
        weight_1 = [0] * num
        for idx, ss in enumerate(strs):
            for ch in ss:
                if ch=='1':
                    weight_1[idx] += 1
                else:
                    weight_0[idx] += 1
        # print(weight_0)
        # print(weight_1)
        # 初始化
        # 非 0 索引肯定初始化为 0 没问题，要取 max 操作
        # 第一行 & 第一列 是否需要额外处理

        # 遍历顺序
        # 遍历物品
        for idx in range(num):
            # 遍历背包 背包是二维的
            # 容量和物品重量的关系在 range 中进行限制
            for i in range(m, weight_0[idx]-1, -1):
                for j in range(n, weight_1[idx]-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-weight_0[idx]][j-weight_1[idx]]+1)
        return dp[m][n]

53-最大子数组和-中等

image-20240722115108440

动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        最大和，连续子数组
        动态规划
        '''
        arr = nums.copy()

        for i in range(1, len(arr)):
            arr[i] = max(arr[i], arr[i-1]+arr[i])
        return max(arr)

918-环形子数组的最大和-中等

image-20240722115121213

image-20240722115133336

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        '''
        环形数组
        最大子数组的两种情况：
        1. 包含首尾：中间即为最小子数组，求最小子数组和
        2. 不包含首尾
        
        维护最大前缀和 & 最小前缀和
        '''
        n = len(nums)
        max_ = float('-inf')
        min_ = float('inf')

        # 无环
        pre = 0     # 以nums[i]结尾的最大前缀和
        for i in range(n):
            if pre > 0:
                pre = pre + nums[i]
            else:
                pre = nums[i]
            max_ = max(max_, pre)
        # 如果最大子数组和小于0，说明数组全是负数，返回最大的负数即可
        if max_<0:
            return max(nums)
        # 有环
        pre = 0     # 以nums[i]结尾的最小前缀和
        for i in range(n):
            if pre > 0:
                pre = nums[i]
            else:
                pre = pre + nums[i]
            min_ = min(min_, pre)
        
        return max(max_, sum(nums)-min_)

一维动态规划

70-爬楼梯-简单

image-20240716125146271

看示例，我们当前应该是处于第0阶

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

198-打家劫舍-中等-记住

image-20240716143043039

class Solution:
    def rob(self, nums: List[int]) -> int:
        '''
        相邻的不能偷
        '''

        n = len(nums)
        dp = [0] * (n+1)
        # dp[i]表示偷窃前i个房子满足条件获得的最大值
        # dp[i]考虑当前nums[i-1]偷还是不偷
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return dp[n]

空间优化

class Solution:
    def rob(self, nums: List[int]) -> int:
        '''
        很多时候我们并不需要始终持有全部的 DP 数组
        对于小偷问题，我们发现，最后一步计算 f(n) 的时候，实际上只用到了 f(n−1) 和 f(n−2) 的结果
        只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题
        '''
        prev = 0
        curr = 0
        for i in nums:
            # 循环开始时，curr表示dp[i-1]，prev表示dp[i-2]
            prev, curr = curr, max(curr, prev+i)
            # 循环结束时，curr表示dp[i]，prev表示dp[i-1]
        return curr

139-单词拆分-中等

image-20240716145854162

动态规划

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        '''
        回溯算法超时

        动态规划，表示字符串s的前i个字母是否能够被表示
        '''
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(n): # 起点
            for j in range(i+1, n+1):
                if dp[i] and s[i:j] in wordDict:
                    dp[j] = True
        return dp[-1]

记忆化回溯

对剩余字符串进行递归调用，将剩余字符串的调用结果进行缓存

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        '''
        记忆化回溯
        使用装饰器，装饰器可以保存函数的执行结果，缓存
        '''
        import functools

        # 使用lru_cache装饰器来缓存back_track函数的结果，None参数表示缓存所有调用的结果，有助于避免重复计算
        @functools.lru_cache(None)
        def back_track(s: str):
            # s为剩余需要匹配的字符串
            if not s:
                return True
            res = False
            for i in range(1, len(s)+1):
                if s[:i] in wordDict:
                    res = back_track(s[i:]) or res
            return res
        return back_track(s)

322-零钱兑换-中等

image-20240716153237892

动态规划

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        ''' 
        不同面额的硬币
        总金额
        凑成总金额所需的最少金币数
        '''
        dp = [math.inf] * (amount+1)
        dp[0] = 0
        for i in coins:
            if i<=amount:
                dp[i] = 1
        for i in range(1, amount+1):
            if dp[i] != math.inf:
                continue
            for j in coins:
                if i-j >=1:
                    dp[i] = min(dp[i], dp[i-j]+1)
                else:
                    continue
        if dp[-1] == math.inf:
            return -1
        return dp[-1]

完全背包问题

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        n = amount
        dp = [math.inf] * (n+1)
        dp[0] = 0

        # 遍历物品
        for coin in coins:
            # 遍历背包
            for i in range(coin, n+1):
                dp[i] = min(dp[i], dp[i-coin]+1)

        if dp[-1] == math.inf:
            return -1
        return dp[-1]

300-最长递增子序列-中等

image-20240716155546512

动态规划

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        '''
        最长增长子序列
        整数数组，严格递增 子序列 相对顺序不改变
        '''
        n = len(nums)
        dp = [1] * n 
        # dp[i] 表示到i为止最长的递增子序列
        for i in range(n):
            for j in range(i, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

多维动态规划

120-三角形最小路径和

image-20240716160749206

动态规划，填充主对角线左侧三角区域

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        '''
        只能移动到下一行的相邻结点
        二维dp数组
        '''
        n = len(triangle)
        dp = [[math.inf for _ in range(n)] for _ in range(n)]
        dp[0][0] = triangle[0][0]
        # 从第二行开始处理
        for i in range(1, n):
            for j in range(i+1):
                # 当前坐标 (i, j)
                if j-1>=0:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
                else:
                    dp[i][j] = dp[i-1][j] + triangle[i][j]
        return min(dp[-1])

64-最小路径和-中等

image-20240716161750047

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        '''
        每次只能向右或向下
        '''
        m = len(grid)
        n = len(grid[0])
        dp = [[math.inf for _ in range(n)]for _ in range(m)]
        # 初始化第一行
        for i in range(n):
            dp[0][i] = grid[0][i]
            if i>0:
                dp[0][i] += dp[0][i-1]
        # 初始化第一列
        for i in range(m):
            dp[i][0] = grid[i][0]
            if i>0:
                dp[i][0] += dp[i-1][0]
        # 遍历
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

63-不同路径Ⅱ-中等

image-20240716163712206

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        '''
        向下或向右
        二维dp数组记录到大当前位置有几种路径
        '''
        # 如果起始位置有石头，直接返回0
        if obstacleGrid[0][0] == 1:
            return 0

        m  = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0 for _ in range(n)]for _ in range(m)]
        dp[0][0] = 1
        # 初始化第一行
        i = 1
        while i<n:
            if obstacleGrid[0][i] == 1:
                break
            dp[0][i] = 1
            i += 1
        while i<n:
            dp[0][i] = 0
            i += 1
        # 初始化第一列
        i = 1
        while i<m:
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
            i += 1
        while i<m:
            dp[i][0] = 0
            i += 1
        # 遍历
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                elif dp[i-1][j] != 0 and dp[i][j-1] != 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

5-最长回文子串-中等

image-20240717105045874

❌错误的中心扩散法

这样选定中心点，同时向两边扩散，只能处理回文子串为奇数的情况，无法处理偶数的情况，如上述bb

class Solution:
    def longestPalindrome(self, s: str) -> str:
        '''
        中心扩散法
        '''
        max_len = 1
        res = s[0]
        n  =len(s)
        for i in range(n):
            left = i-1
            right = i+1
            while left >=0 and right <= n-1:
                if s[left] != s[right]:
                    break
                if right-left+1>max_len:
                    max_len = right-left+1
                    res = s[left:right+1]
                left -= 1
                right += 1

        return res

✔ 正确的中心扩散法

考虑当前中心点时，应将左右指针分别移动到不等于中心点处，再向左右扩展

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ''
        n = len(s)
        cur_len = 1  # ! 初始化为1
        max_len = 1
        res = s[0]

        for i in range(n):
            left = i-1
            right = i+1
            # 向左扩展回文子串
            while left>=0 and s[left] == s[i]:
                cur_len += 1
                left -= 1
            # 向右扩展回文子串
            while right<=n-1 and s[right] == s[i]:
                cur_len += 1
                right += 1
            # 上面的代码解决当中心点左右两侧与中心点字符相同的情况
            # 将left和right移动到与中心点不同的位置
            # 左右向两侧扩展
            while left >=0 and right <=n-1 and s[left]==s[right]:
                cur_len += 2
                left -= 1
                right += 1
            if cur_len > max_len:
                max_len = cur_len
                res = s[left+1: right]
            cur_len = 1
        return res

动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        '''
        dp[l][r] 表示字符从l到r是否为回文串
        如果要判断dp[l-1][r+1]是否为回文串，必须dp[l][r]是回文，且s[l-1]==s[r+1]
        '''
        max_len = 0
        n = len(s)
        if n<2:
            return s 
        res = s[0]
        dp = [[False for _ in range(n)]for _ in range(n)]
        # 初始化，对角线处为True
        for i in range(n):
            dp[i][i] = True 
        # 遍历
        # 先枚举子串的长度
        for L in range(2, n+1):
            # 左边界
            for l in range(n):
                # 右边界
                r = l+L-1
                if r>n-1:
                    break
                if s[l] != s[r]:
                    dp[l][r] = False
                else:
                    if r-l<3: # 

标签：int,max,len,力扣,range,prices,全解,动态,dp	

From： https://www.cnblogs.com/mudou/p/18315769

相关文章

  • 力扣6. Z 字形变换
    将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：PAHNAPLSIIGYIR之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。......
  • 通过django admin添加动态字段
    我环顾了堆栈，但找不到任何答案。所以我有一个像这样的模型：classDynamicModel(models.Model):config=models.JSONField()def__str__(self):returnself.config我现在想要做的是将json字段键值对显示为独立字段，并且还能够以相同的方式编辑它们，就......
  • 等保测评与ISO27001认证的区别全解析
    等保测评与ISO27001认证的区别全解析问题：等保测评与ISO27001认证有什么区别？回答：等保测评和ISO27001认证都是信息安全领域的重要标准，但它们在适用范围、标准要求、实施流程等方面存在显著差异。以下是详细解析：1.适用范围等保测评（信息安全等级保护）：适用对象：主要适用于......
  • Redis底层数据结构-简单动态字符串SDS
    简单动态字符串（simpledynamicstring，SDS）。Redis没有直接使用C语言传统的字符串，而是自己构建了一种简单动态字符串(SDS)的抽象类型。C字符串只会作为字符串字面量（stringliteral）用在一些无须对字符串值进行修改的地方。实现sds.h/sdshdrstruct__attribute__((__packed__)......
  • 追踪动态世界：视频流中的目标跟踪及其与目标检测的紧密联系
    追踪动态世界：视频流中的目标跟踪及其与目标检测的紧密联系在视频监控、自动驾驶、体育分析等领域，视频流中的目标跟踪是一项至关重要的技术。它不仅能够识别视频中的物体，还能在视频帧序列中持续追踪这些物体的位置和运动。目标跟踪与目标检测密切相关，目标检测是跟踪过程的起......
  • 时间序列分析方法汇总对比及优缺点和适用情况（下）-- 11. 卡尔曼滤波 12. 广义自回归条件
    目录11.卡尔曼滤波（KalmanFilter）12.广义自回归条件异方差模型（GARCH）13.贝叶斯结构时间序列模型（BayesianStructuralTimeSeries,BSTS）14.动态因子模型（DynamicFactorModel,DFM）15.隐马尔科夫模型（HiddenMarkovModel,HMM）16.分段线性回归（PiecewiseLinearRegress......
  • 对类的属性动态排序
    publicstaticvoidsortByField(List<User>list,StringfieldName){list.sort((u1,u2)->{try{Objectvalue1=User.class.getDeclaredMethod("get"+capitalize(fieldName)).invoke(u1);......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99