基于python的leetcode算法介绍之动态规划

文章目录

  • 零 算法介绍
  • 一 例题介绍 使用最小花费爬楼梯
    • 问题分析
  • Leetcode例题与思路
    • [118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/)
      • 解题思路
      • 题解
    • [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)
      • 解题思路
      • 题解
    • [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/)
      • 解题思路
      • 题解
    • [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)
      • 解题思路
      • 题解
    • [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/)
      • 解题思路
      • 题解

零 算法介绍

动态规划(Dynamic Programming,DP)是一种解决最优化问题的算法思想,通过将问题分解成更小的子问题来解决。其核心思想是将一个问题分解成更小的、相互独立的子问题,然后将子问题的解组合起来,形成原问题的解。但与之前的算法不一样的是,动态规划强调的是动态的过程,即在程序计算时,会出现随程序运行而变化的参数辅助程序完成算法计算。

动态规划算法的主要特点包括:

  1. 重叠子问题:动态规划算法解决的问题通常包含许多重叠的子问题。

  2. 状态转移方程:动态规划算法通常使用状态转移方程来描述问题的状态和状态转移关系。

  3. 自底向上:动态规划算法通常采用自底向上的方法,即从最小的子问题开始解决,逐步解决更大的子问题。

动态规划算法的应用范围非常广泛,包括:

  1. 组合优化问题:如背包问题、旅行商问题等。

  2. 序列问题:如最长公共子序列、最长递增子序列等。

  3. 图论问题:如最短路径问题、最小生成树问题等。

  4. 动态规划在游戏、人工智能、计算机图形学等领域也有广泛应用。

动态规划算法有很多变种,如线性动态规划、树形动态规划、网格动态规划等。在实际应用中,需要根据问题的特点选择合适的动态规划算法。

一 例题介绍 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

问题分析

动态规划强调的是动态的过程, 故当我们再看这道题目的时候,我们的关注点是 一旦你支付此费用,即可选择向上爬一个或者两个台阶。 当我们转换一下思路,则是:当前台阶的价值应该是由前一个台阶或是前前一个台阶决定的。如果这套规则适用的话,则代表第N阶的台阶等于total[n] = min(total[n-1]+cost[n-1], total[n-2]+cost[n-2])。即,当前台阶的最低花费应该是在上两级台阶的最小开销中进行选择。

代码呈现如下:

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        old1, old2 = 0, 0     # 初始化前前一个台阶和前一个台阶的初始价格
        for i in cost:        # 对所有台阶遍历
            temp = i + min(old1, old2)     # 第N个台阶的花费是当前第N个台阶的价格加上前两级台阶中小的那个
            old1, old2 = old2, temp        # 迭代
        return min(old1, old2)

Leetcode例题与思路

接下来,我们列举关于Leetcode的几道例题,并通过动态规划的方式进行求解:

118. 杨辉三角

给定一个非负整数 *numRows,*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

解题思路

这道题目是最简单的动态规划题目,对于第N行来说,其第1个和最后一个应当为1,其余位置可以通过上一行中当前位置和当前位置的下一位置两个元素求和完成。转换成代码如下所示:

题解

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(numRows):
            row = [None for _ in range(i + 1)]
            row[0], row[-1] = 1, 1
            for j in range(1, len(row) - 1):
                row[j] = res[i - 1][j - 1] + res[i - 1][j]
            res.append(row)
        return res

53. 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

解题思路

由于这边仅需要找到最大和,无需判断位置。故我们仅需判断最大值作为我们的判断。那么最大子数组和应该有什么特点呢?其实从这道题目中我们就会发现从哪开始到哪结束是不重要的。需要关注的是在第N个元素的位置,我们之前的元素和大于零还是小于零。什么意思呢?即之前元素之和如果小于0,那么对于后续元素求和只有负面效果,故可以直接丢弃从第N个元素开始重新统计。而我们只需要在这个过程中,找到累计和最大的值就可以了。由题目的提示可知,-10^4 <= nums[i] <= 10^4。故我们可以选择-10000作为初始化:

题解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp, max_value = -10000, -10000
        for i in nums:
            temp = max(temp + i, i)
            max_value = max(temp, max_value)
        return max_value

96. 不同的二叉搜索树

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

在这里插入图片描述

解题思路

首先我们需要明确一个概念,什么是二叉搜索树:

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,它的每个节点都有一个关键值,并且所有节点的关键值满足以下性质:

  1. 节点的左子树(如果存在)的关键值都小于节点的关键值。

  2. 节点的右子树(如果存在)的关键值都大于节点的关键值。

  3. 节点的左右子树(如果存在)也都是二叉搜索树。

这种结构使得二叉搜索树在查找、插入和删除操作方面具有较高的效率。

那么面对这样一道题,我们该如何求解呢?首先,我们需要明确一个问题,就是对于N个节点的二叉树,我们可以把这个二叉树从节点切分,分为成小于该长度的二叉树来求解。换句话说,我们在面对一个4节点的二叉搜索树,可以看作013[代表左子树0,根节点1,右节点3],112, 211 , 310。所以我们仅需要得到1节点,2节点和3节点的树就可以推出4节点的数量。那么我们可以快速推出,0节点仅存在1种排列,1节点仅存在1种排列。从2节点开始,我们可以通过公式进行推理:N节点的树可以看作N个根和他们的左右子树。故,我们可以通过左子树的种类乘以右子树的种类得到每个节点存在子树的个数。继续以4节点树为例,可以分为013112, 211 , 310。当我们知道0,1,2,3个节点的数量时,就可以得到013[1*5]112[1*2], 211[2*1] , 310[5*1]。故四节点可以构建5+2+2+5=14个排列。

题解

class Solution:
    def numTrees(self, n: int) -> int:
        node_list = [1 for i in range(0, n+1)]
        for i in range(2, n+1):
            node_list[i] = sum([node_list[j] * node_list[i-j-1] for j in range(i)])
        return node_list[-1]

322. 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

解题思路

这道题目可以转换成走楼梯的思路。如果还不能get到这个思路的话,我们再细说一下:

针对N块钱,凑出来的方法必然是考虑N块钱前一步的状态,即N块钱减去coins的状态下需要多少步。所以我们从coins最小的储蓄开始执行,通过对比上一步的所有状态,选择其中需要部署最小的作为自己的结果,一直到amount,得到最终结果。

题解

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        answer = [-1 for i in range(amount+1)]             # 初始化所有状态
        answer[0] = 0                                      # 初始化0,这样coins中的所有元素的步长都为1
        for i in range(min(coins), amount+1):              # 计算到amount的步长
            mins = 2**31
            for j in coins:                                # 对比coins中的所有状态
                if i - j >= 0 and answer[i - j] > -1:      # 当上一状态合法且存在时,获得最小步数
                    mins = min(answer[i - j] + 1, mins)
            answer[i] = mins if mins != 2**31 else -1      # 更新当前状态
        return answer[-1]

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

解题思路

这是一道将动态规划运用到树上的一道题,结合了树的搜索,故还需要用到递归的方法进行搜索。

我们对其中任意节点进行思考,如何判断当前节点以下的树节点应当被省略?即会降低全局解的情况,也就是当前节点联通的路径小于0的情况下。那怎么得到当前节点的联通路径呢?即根节点和左子树与右子树中较大的值的和。故我们需要注意,**左子树和右子树的返回结果是必然大于0的,否则就没有链接的必要。**那如果不回调的话,最大联通树应该是当前节点加上左节点加上右节点的值,如果当前值大于已知的最大值,那么就可以替换当前的最大值。

题解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.answer = -1000
        self.maxroot(root)
        return self.answer

    def maxroot(self, root):
        if root == None:
            return 0
        else:
            left = self.maxroot(root.left)
            right = self.maxroot(root.right)
            self.answer = max(self.answer, root.val + left + right)
            return max(max(left, right) + root.val, 0)

以上就是最基础的动态规划,动态规划的题目难度非常大,后续有精力会详细拆开,深入剖析。

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

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

相关文章

自动驾驶预测-决策-规划-控制学习(4):预测分析文献阅读

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、摘要分析1.Transformer模型是什么&#xff1f;什么是自注意力机制&#xff1f; 2.数据集是什么&#xff1f;3.预测车辆行驶轨迹和车辆换道意图4. LSTM 网络…

Pytest成魔之路 —— fixture 之大解剖!

1. 简介 fixture是pytest的一个闪光点&#xff0c;pytest要精通怎么能不学习fixture呢&#xff1f;跟着我一起深入学习fixture吧。其实unittest和nose都支持fixture&#xff0c;但是pytest做得更炫。 fixture是pytest特有的功能&#xff0c;它用pytest.fixture标识&#xff0c…

MybatisPlus—快速入门

目录 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 1.2 定义Mapper 2.MybatisPlus常用注解 2.1 TableName 2.2 TableId 2.3 TableField 2.4 小结 3. 常用配置 4. 总结 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 MyBatisPlus官方提…

如何使用 NFTScan NFT API 在 PlatON 网络上开发 Web3 应用

PlatON 是由万向区块链和矩阵元主导开发的面向下一代的全球计算架构&#xff0c;创新性的采用元计算框架 Monad 和基于 Reload 覆盖网络的同构多链架构&#xff0c;其愿景是成为全球首个提供完备隐私保护能力的运营服务网络。它提供计算、存储、通讯服务&#xff0c;并提供算力…

软件测试|什么是Python构造方法,构造方法如何使用?

构造方法&#xff08;Constructor&#xff09;是面向对象编程中的重要概念&#xff0c;它在创建对象时用于初始化对象的实例变量。在Python中&#xff0c;构造方法是通过特殊的名称__init__()来定义的。本文将介绍Python构造方法的基本概念、语法和用法。 什么是构造方法&…

React使用动态标签名称

最近在一项目里&#xff08;React antd&#xff09;遇到一个需求&#xff0c;某项基础信息里有个图标配置&#xff08;图标用的是antd的Icon组件&#xff09;&#xff0c;该项基础信息的图标信息修改后&#xff0c;存于后台数据库&#xff0c;后台数据库里存的是antd Icon组件…

ArkTS - 网络请求

一、Axios请求 应用通过HTTP发起一个数据请求&#xff0c;支持常见的GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE、CONNECT方法。 前端开发肯定都使用过一个叫axios的第三方库&#xff0c;它是是一个基于 promise 的网络请求库&#xff0c;可以用于浏览器和 node.js&…

Rust 字符串 初步了解

rust 的字符串 。字符串不是复合类型&#xff0c; String 和 &str &#xff1a; String 具有所有权&#xff0c;是存储在堆上的。&str 没有所有权&#xff0c;是对 String 的引用。字符串字面量也是 &str 类型&#xff0c;存储在栈上。 切片&#xff08;slice&a…

Nacos与Eureka

一、前言 在构建和管理微服务架构时&#xff0c;选择适当的服务注册中心至关重要。Nacos和Eureka都是微服务体系结构中常用的服务注册和发现工具。本文将探讨它们之间的区别&#xff0c;帮助开发者在选择适合其项目需求的注册中心时做出明智的决策。 二、架构和适用场景 Nacos …

TSConfig 配置(tsconfig.json)

详细总结一下TSConfig 的相关配置项。个人笔记&#xff0c;仅供参考&#xff0c;欢迎批评指正&#xff01; 另外&#xff0c;如果想了解更多ts相关知识&#xff0c;可以参考我的其他笔记&#xff1a; vue3ts开发干货笔记ts相关笔记&#xff08;基础必看&#xff09;ts相关笔记…

【linux笔记1】

目录 【linux笔记1】文件内容的理解用户管理用户管理命令添加用户切换用户修改用户信息删除用户 用户组 【linux笔记1】 文件内容的理解 etc文件夹&#xff1a;etc是拉丁语"et cetera"的缩写&#xff0c;意思是“和其他的”或“等等”。在linux系统中&#xff0c;“…

YOLOv5改进 | 卷积篇 | SAConv轻量化的可切换空洞卷积(附修改后的C3+Bottleneck)

一、本文介绍 本文给大家带来的改进机制是可切换的空洞卷积(Switchable Atrous Convolution, SAC)是一种创新的卷积网络机制,专为增强物体检测和分割任务中的特征提取而设计。SAC的核心思想是在相同的输入特征上应用不同的空洞率进行卷积,并通过特别设计的开关函数来融合这…

sensor 点亮出图后,画面全黑是为什么?

同事在点一个思特威的 sensor sc035hgs&#xff0c;这个 sensor 主要负责数据采集&#xff0c;然后给到后面的 NN&#xff08;神经网络&#xff09;去做处理。 点亮出图后&#xff0c;画面很黑&#xff0c;如下图所示&#xff1a; 因为没拿到板子&#xff0c;只能盲猜&#xf…

[蓝桥 2023 ]三带一

问题描述 小蓝和小桥玩斗地主&#xff0c;小蓝只剩四张牌了&#xff0c;他想知道是否是“三带一”牌型。 所谓“三带一”牌型&#xff0c;即四张手牌中&#xff0c;有三张牌一样&#xff0c;另外一张不与其他牌相同&#xff0c;换种说法&#xff0c;四张手牌经过重新排列后&am…

企业档案集中式管理什么意思?企业档案集中式管理的特点

企业档案集中式管理是指将企业所有的档案资料集中存放、管理和维护的一种方式。在集中式管理中&#xff0c;企业将所有的档案资料集中存放在一个统一的档案中心或档案馆中&#xff0c;通过专门的档案管理人员负责对档案资料进行分类、整理、存储和检索&#xff0c;确保档案资料…

Linux操作系统基础(12):Linux的Shell解释器

1. Shell的介绍 在Linux中&#xff0c;Shell 是一种命令行解释器&#xff0c;它是用户与操作系统内核之间的接口&#xff0c;它负责解释用户输入的命令&#xff0c;并将其转换成系统调用或其他操作系统能够执行的指令。 Shell 提供了一种交互式的方式来与操作系统进行通信&am…

Apache Doris 2.0.2 安装步骤 Centos8

Linux 操作系统版本需求 Linux 系统版本当前系统版本CentOS7.1 及以上CentOS8Ubuntu16.04 及以上- 软件需求 软件版本当前版本Java1.81.8.0_391GCC4.8.2 及以上gcc (GCC) 8.5.0 20210514 (Red Hat 8.5.0-4) 1、查看操作系统版本 方法 1&#xff1a;使用命令行 打开终端或…

第九节HarmonyOS 常用基础组件9-TextArea

1、描述 多行文本输入框组件&#xff0c;当输入的文本内容超过组件宽度时会自动换行显示。 2、接口 TextArea(value?:{placeholder?: ResourceStr, text?: ResourceStr, controller?: TextAreaController}) 3、参数 参数名 参数类型 必填 描述 placeholder Resour…

通信原理期末复习——计算大题(一)

个人名片&#xff1a; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的在校大学生 &#x1f42f;个人主页&#xff1a;妄北y &#x1f427;个人QQ&#xff1a;2061314755 &#x1f43b;个人邮箱&#xff1a;2061314755qq.com &#x1f989;个人WeChat&#xff1a;V…

攀登者2 - 华为OD统一考试

OD统一考试 分值: 200分 题解: Java / Python / C++ 题目描述 攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。 地图表示为一维数组,数组的索引代表水平位置,数组的元素代表相对海拔高度。其中数组元素0代表地面。 例如:[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0],代表如下…