Python - 深夜数据结构与算法之 DP 串讲

目录

一.引言

二.DP 知识点回顾

1.递归

2.分治

3.动态规划

三.DP 经典题目回顾

1.Climb-Stairs [70]

2.Unique-Paths [62]

3.House-Robber [198]

4.Min-Path-Sum [64]

5.Best-Time-Sell-Stock [121]

6.Min-Cost-Climb [746]

7.Edit-Distance [72]

8.Longest-Sub-Seq [300]

四.总结

一.引言

动态规划 DP 作为算法里比较晦涩难懂的一部分，我们这里多多复习几遍也不为过。本文主要重温递归、分治、回溯以及状态转移方程的概念，同时复习一下之前做过的题目。

二.DP 知识点回顾

1.递归

2.分治

3.动态规划

复杂的问题转换为子问题 - 分治 & 最优子结构 - 递推到 n :

三.DP 经典题目回顾

1.Climb-Stairs [70]

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

◆ 题目分析

爬楼梯一次可以走1步或者2步，因此推导出 f(n) = f(n-1) + f(n-2)，与 Fib 异曲同工。

◆ 傻递归

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

傻递归存在大量的重复计算，基本都会超时。 

◆ 递归 + Cache

class Solution(object):

    def __init__(self):
        self.mem = {0:0, 1:1, 2:2}

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n in self.mem:
            return self.mem[n]

        steps = self.climbStairs(n-1) + self.climbStairs(n-2)
        self.mem[n] = steps
        return self.mem[n]

加 Cache 的通法，在 init 初始化 cache，在傻递归返回的时候存入 cache 避免重复计算。 

◆ DP Table

class Solution(object):

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n <= 2:
            return n

        a, b = 1, 2
        for i in range(1, n):
            a, b = b, a+b
        
        return a

使用 DP Table 时如果只使用有限个状态，一般都可以使用几个变量完成 dp 推进。 

2.Unique-Paths [62]

不同路径: https://leetcode.cn/problems/unique-paths/

◆ 题目思路 

◆ DP Table

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        dp = [[0] * n for _ in range(m)]
        for i in range(n):
            dp[0][i] = 1

        for j in range(m):
            dp[j][0] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

dp[i][j] = dp[i-1][j] + dp[i][j-1] 即新位置等于左边和上面的位置之和。

◆ combination 

class Solution(object):

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        total = m + n - 2

        # 减少计算量
        if m > n:
            k = n - 1
        else:
            k = m - 1

        A = 1
        F = 1

        for i in range(k):
            A *= total
            total -= 1
            F *= k
            k -= 1

        return A // F

可以转化为排列组合问题，M+N-2 种走法，只要 M-1 向右，N-1 向下即可，直接套用 C(n,k)。

3.House-Robber [198]

打家劫舍: https://leetcode-cn.com/problems/house-robber/

◆ 题目分析

◆ DP 转移

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # 两个状态代表偷不偷
        dp = [[0, 0] for _ in range(len(nums))]
        dp[0][1] = nums[0]

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

[0]、[1] 两个状态代表偷或者不偷，遍历即可。 

◆ 空间优化

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        pre, now = 0, 0

        for i in nums:
            pre, now = now, max(pre + i, now)

        return now

当前状态只与前两次状态有关，所以可以压缩 DP 状态空间。 

4.Min-Path-Sum [64]

最小路径和: https://leetcode-cn.com/problems/minimum-path-sum/

◆ 题目分析

◆ DP 状态

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        M, N = len(grid), len(grid[0])

        # 遍历行
        for col in range(1, N):
            grid[0][col] += grid[0][col-1]

        # 遍历行
        for row in range(1, M):
            grid[row][0] += grid[row - 1][0]

        # 遍历内部元素
        for row in range(1, M):
            for col in range(1, N):
                grid[row][col] += min(grid[row - 1][col], grid[row][col - 1])
        
        return grid[M - 1][N - 1]

每一步的最小值等于当前位置加上左边或上面的最小值。

5.Best-Time-Sell-Stock [121]

股票买卖: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

◆ 题目分析

上面为股票问题的 dp 套路模版，其中 dp 空间 i 为天数，k 为交易次数，s 为是否持有股票。

要维持没有股票的状态，只能 rest 或者卖，要维持有股票的状态，只能 rest 或者买。

rest 代表保持状态，buy 时因为要从 Profit 中付出代价，所以要减去 prices[i]。

◆ DP 状态

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        # dp[i] = max(dp[i] - pre_min, dp[i-1])

        dp = [0] * len(prices)
        pre_min = prices[0]

        for i in range(1, len(prices)):
            dp[i] = max(prices[i] - pre_min, dp[i-1])
            if pre_min > prices[i]:
                pre_min = prices[i]

        return dp[-1]

dp[i] = max(dp[i] - pre_min, dp[i-1]) 当前位置等于卖了和上一次的最大值。

◆ DP + 双指针

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        # dp[i] = max(dp[i] - pre_min, 0)

        cur_min = prices[0]
        cur_max = 0

        for i in range(1, len(prices)):
            cur_max = max(cur_max, prices[i] - cur_min)
            cur_min = min(cur_min, prices[i])
        
        return cur_max

每次维护 max 和 min 即可。 

6.Min-Cost-Climb [746]

最小花费爬楼梯: https://leetcode.cn/problems/min-cost-climbing-stairs/description/

◆ 题目分析

到达第 i 个楼梯，起点是 0 级或 1 级台阶。我们到达 i 级台阶的费用:

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

由于起始点 0,1 都可以自由选择，所以其初始化为 0 。

 ◆ DP 实现

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """

        # dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-1])

        dp = [0] * (len(cost) + 1)

        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        return dp[-1]

这个题比较坑的点是楼顶对应索引 n，而索引从 0 开始，所以需要遍历 range(0, n+1)。不过题目的状态转移方程还是很漂亮，借鉴了前面爬楼梯的题目。 

7.Edit-Distance [72]

编辑距离: https://leetcode-cn.com/problems/edit-distance/

◆ 题目分析

 这个题和之前的单词接龙比较像，但是一拿到又无从下手，这里直接给出 DP 的思路，构建二维 DP 状态矩阵，大小为 [M+1, N+1]，如果 w1[i] == w2[j] 字符相同，那么此处无需操作；否则我们需要借助插入、删除、替换的操作，这里插入和删除其实是相对的，无需严格的区分:

所以 dp[i][j] 的最小编辑距离就可以从 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 里找最小再 + 1。这个题好写但是难想，把上面的 dp table 写出来更方便理解，这里理解不好就记忆好了，也不错。

◆ DP 实现

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # w[i] = w[j] -> w[i][j] = w[i-1]w[j-1]
        # w[i] != w[j] -> w[i][j] = min(w[i-1][j-1] + 1, w[i-1][j] + 1, w[i][j-1] +1)

        M, N = len(word1), len(word2)

        # 状态空间
        dp = [[0] * (N + 1) for _ in range(M + 1)]

        #
        for i in range(M + 1):
            dp[i][0] = i
        for j in range(N + 1):
            dp[0][j] = j

        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

        return dp[-1][-1]

8.Longest-Sub-Seq [300]

 最长递增子序列: https://leetcode.cn/problems/longest-increasing-subsequence

◆ 题目分析 

对于 i 位置，其等于 range(0, i) 之间的元素，如果 nums[i] > nums[j] 则 dp[i] = max_sub + 1。

◆ DP 实现

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

四.总结

如果同学们是看了前面 DP 和 DP 进阶并且做了习题的话，相信今天再看这一个章节会有一种醍醐灌顶，豁然开朗的状态，后面我们会继续讲解回顾高级 DP 动态规划问题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/328011.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

AI大模型预先学习笔记一：transformer和fine tune技术介绍

AI大模型预先学习笔记一：transformer和fine tune技术介绍

一、商业观点&#xff1a;企业借助大模型获得业务增长可能 二、底层原理&#xff1a;transformer 1&#xff09;备注 ①下面每个步骤都是自回归的过程&#xff08;aotu-regressive&#xff09;&#xff1a;已输出内容的每个字作为输入&#xff0c;一起生成下一个字 ②合起来就…
阅读更多...
决战排序之巅（二）

决战排序之巅（二）

决战排序之巅&#xff08;二&#xff09; 排序测试函数 void verify(int* arr, int n) 归并排序递归方案代码可行性测试 非递归方案代码可行性测试 特点分析 计数排序代码实现代码可行性测试 特点分析 归并排序 VS 计数排序&#xff08;Release版本&#xff09;说明1w rand( ) …
阅读更多...
23/76-LeNet

23/76-LeNet

LeNet 早期成功的神经网络。 先使用卷积层来学习图片空间信息。 然后使用全连接层转换到类别空间。 #In[]LeNet,上世纪80年代的产物,最初为了手写识别设计from d2l import torch as d2l import torch from torch import nn from torch.nn.modules.loss import CrossEntropyLos…
阅读更多...
Transformer详解（附代码实现及翻译任务实现）

Transformer详解（附代码实现及翻译任务实现）

一&#xff1a;了解背景和动机 阅读Transformer论文&#xff1a; 阅读原始的Transformer论文&#xff1a;“Attention is All You Need”&#xff0c;由Vaswani等人于2017年提出&#xff0c;是Transformer模型的开创性工作。 二&#xff1a;理解基本构建块 注意力机制&#…
阅读更多...
C++面试宝典第21题：字符串解码

C++面试宝典第21题：字符串解码

题目 给定一个经过编码的字符串，返回其解码后的字符串。具体的编码规则为：k[encoded_string]，表示方括号内部的encoded_string正好重复k次。注意：k保证为正整数；encoded_string只包含大小写字母，不包含空格和数字；方括号确定是匹配的，且可以嵌套。 示例： 编码字符串为…
阅读更多...
tcpdump常用参数以及wireshark密文解密

tcpdump常用参数以及wireshark密文解密

tcpdump常用参数以及wireshark密文解密 文章目录 一、tcpdump命令和常用参数二、在wireshark中协议解析 tcpdump常用参数 一、tcpdump命令和常用参数 tcpdump常用命令&#xff1a;tcpdump -i eth0 src host 11.6.224.1 and udp port 161 -s 0 -w 161.pcap &#xff08;161为sn…
阅读更多...
开发知识点-JAVA-springboot

开发知识点-JAVA-springboot

springboot springbootConfiguration注解的底层核心原理Bean注解的底层核心原理 springboot Configuration注解的底层核心原理 https://www.bilibili.com/video/BV1rq4y1E7gK/?spm_id_from333.999.0.0&vd_sourcef21773b7086456ae21a58a6cc59023be spring.io 全家桶 24…
阅读更多...
Mysql 数据库DDL 数据定义语言——数据库，数据表的创建

Mysql 数据库DDL 数据定义语言——数据库，数据表的创建

DDL&#xff1a;数据定义语言&#xff0c;用来定义数据库对象&#xff08;数据库&#xff0c;表&#xff0c;字段&#xff09;—Database Definition Language 1、登录数据库&#xff0c;输入用户名和密码 mysql -ufdd -p990107Wjl2、查看数据库 show databases;3、创建一个…
阅读更多...
主流人工智能AI工具测评

主流人工智能AI工具测评

主流人工智能AI工具测评 主流的人工智能AI工具ChatGPT ——OpenAI研发CHAT_BISON——Google研发Qwen通义千问 ——阿里云研发文心一言——百度研发 根据10个问题分析人工智能的回答女朋友生气了怎么哄千元机性价比推荐小米13 和 vivo iQOO 11s哪个好计算机专业毕业论文护士年终…
阅读更多...
node.js(expree.js )模拟手机验证码功能及登录功能

node.js(expree.js )模拟手机验证码功能及登录功能

dbconfig.js const mysql require(mysql) module.exports {// 数据库配置config: {host: localhost, // 连接地址port: 3306, //端口号user: root, //用户名password: wei630229, //密码database: exapp2, //数据库名}, // 连接数据库&#xff0c;使用mysql的连接池连接方式…
阅读更多...
transfomer的位置编码

transfomer的位置编码

什么是位置编码 在transformer的encoder和decoder的输入层中&#xff0c;使用了Positional Encoding&#xff0c;使得最终的输入满足&#xff1a; input_embeddingpositional_encoding 这里&#xff0c;input_embedding的shape为[n,b,embed_dim],positional_encoding和input_…
阅读更多...
xilinxi mulitboot 启动

xilinxi mulitboot 启动

xilinix在线更新有两种方式&#xff0c;一种是使用ICAP原语&#xff0c;另一中是在xdc中约束&#xff0c;根据应用的场景不同&#xff0c;选用不同的启动方式&#xff0c;第二种更为简单。 可参考官方提供的手册和实例 XAPP1247 链接&#xff1a; XAPP1247 golden和updata.b…
阅读更多...
VitePress-01-从零开始的项目创建（npm版）

VitePress-01-从零开始的项目创建（npm版）

说明 本文介绍一下 VitePress的项目创建的步骤。 主要用到的命令工具是 npm。 本文的操作步骤是从无到有的创建一个完整的基本的【VitePress】项目。 环境准备 根据官方文档的介绍&#xff0c;截止本文发稿时&#xff0c;需要使用node.js 18 的版本。 可以使用node -v 的命令查…
阅读更多...
muduo网络库剖析——通道Channel类

muduo网络库剖析——通道Channel类

muduo网络库剖析——通道Channel类 前情从muduo到my_muduo 概要事件种类channel 框架与细节成员函数细节实现使用方法 源码结尾 前情 从muduo到my_muduo 作为一个宏大的、功能健全的muduo库&#xff0c;考虑的肯定是众多情况是否可以高效满足&#xff1b;而作为学习者&#x…
阅读更多...
Asp .Net Core 系列：集成 Ocelot+Consul实现网关、服务注册、服务发现

Asp .Net Core 系列：集成 Ocelot+Consul实现网关、服务注册、服务发现

什么是Ocelot? Ocelot是一个开源的ASP.NET Core微服务网关&#xff0c;它提供了API网关所需的所有功能&#xff0c;如路由、认证、限流、监控等。 Ocelot是一个简单、灵活且功能强大的API网关&#xff0c;它可以与现有的服务集成&#xff0c;并帮助您保护、监控和扩展您的微…
阅读更多...
RTSP/Onvif安防视频监控平台EasyNVR漏洞扫描及解决方法

RTSP/Onvif安防视频监控平台EasyNVR漏洞扫描及解决方法

视频安防监控平台EasyNVR可支持设备通过RTSP/Onvif协议接入&#xff0c;并能对接入的视频流进行处理与多端分发&#xff0c;包括RTSP、RTMP、HTTP-FLV、WS-FLV、HLS、WebRTC等多种格式。安防视频监控平台可提供视频实时监控直播、云端录像、云存储、录像检索与回看、告警等视频…
阅读更多...
【前端架构】前端通用架构

【前端架构】前端通用架构

一个强大的前端通用架构应该具备多种能力&#xff0c;以支持现代化的应用程序开发和提高开发效率。以下是一些前端通用架构应该具备的关键能力&#xff1a; 模块化和组件化&#xff1a;支持模块化开发和组件化架构&#xff0c;能够将应用拆分为独立的模块和组件&#xff0c;以便…
阅读更多...
外观模式（结构型）

外观模式（结构型）

目录 一、前言 二、外观模式 三、总结 一、前言 外观模式&#xff08;Facade Pattern&#xff09;是一种结构型设计模式&#xff0c;它为系统中的一组复杂子系统提供一个简单的接口&#xff0c;从而隐藏了这些子系统的复杂性&#xff0c;并且使得代码更加易于使用和理解。 外…
阅读更多...
XUbuntu22.04之免费开源DesktopNaotu脑图(二百零七)

XUbuntu22.04之免费开源DesktopNaotu脑图(二百零七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
5个99%的人可能不知道的实用程序库!

5个99%的人可能不知道的实用程序库!

前言 作为一名前端开发者,这些 JavaScript 库极大地提高了我的工作效率,如格式化日期、处理 URL 参数和调试移动网页。朋友们,我想和你们分享这些库。 1. 使用 “Day.js” 来格式化日期和时间 链接 作为开发者,我已经厌倦了在 JavaScript 中操作日期和时间,因为它太麻烦了。…
阅读更多...
最新文章

Copyright @ 2022~2023