【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96

2024-06-09 16:44

本文主要是介绍【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96

需强化知识点

  • 思路:343 and 96

题目

343. 整数拆分

  • dp 含义:拆分i,乘积最大值;依次遍历 i的因子,记录最大值,max(之前的因子,两两拆分的情况,多次拆分的情况)
class Solution:def integerBreak(self, n: int) -> int:# 拆分i,乘积最大值dp = [1] * (n+1)for i in range(2, n+1):for j in range(1, i+1):dp[i] = max(max( j * (i-j), dp[j] * (i-j)), dp[i])return dp[n]

96. 不同的二叉搜索树

  • 代码随想录思路
  • dp 的含义:1到i为节点组成的二叉搜索树的个数为dp[i];
  • 递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为 j 为头结点左子树节点数量,i-j 为以 j 为头结点右子树节点数量,依次累加(此处只需要考虑种类数,因此可以直接使用,dp[i - j], 因为数字的大小排序情况是等价的)
  • 注意初始值的赋予:因为此处是累加,不能都赋值为1
class Solution:def numTrees(self, n: int) -> int:#  1到i为节点组成的二叉搜索树的个数为dp[i]。dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n+1):for j in range(1, i+1):dp[i] += dp[j-1] * dp[i-j]return dp[n]

这篇关于【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1045730

相关文章

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

深入解析 Java Future 类及代码示例

《深入解析JavaFuture类及代码示例》JavaFuture是java.util.concurrent包中用于表示异步计算结果的核心接口,下面给大家介绍JavaFuture类及实例代码,感兴... 目录一、Future 类概述二、核心工作机制代码示例执行流程2. 状态机模型3. 核心方法解析行为总结:三

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

pandas实现数据concat拼接的示例代码

《pandas实现数据concat拼接的示例代码》pandas.concat用于合并DataFrame或Series,本文主要介绍了pandas实现数据concat拼接的示例代码,具有一定的参考价值,... 目录语法示例:使用pandas.concat合并数据默认的concat:参数axis=0,join=

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

IIS 7.0 及更高版本中的 FTP 状态代码

《IIS7.0及更高版本中的FTP状态代码》本文介绍IIS7.0中的FTP状态代码,方便大家在使用iis中发现ftp的问题... 简介尝试使用 FTP 访问运行 Internet Information Services (IIS) 7.0 或更高版本的服务器上的内容时,IIS 将返回指示响应状态的数字代