代码随想录算法训练营第40天 | 343. 整数拆分 ,96.不同的二叉搜索树

动态规划章节理论基础:

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

343. 整数拆分

题目链接:https://leetcode.cn/problems/integer-break/

思路:

动规五部曲:
(1)确定dp数组以及下标含义
dp[i]:分拆数字i,可以得到的最大乘积为dp[i]。

(2)确定递归公式
其实可以从1遍历j,然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j],相当于是拆分(i - j)。
j是从1开始遍历,拆分j的情况,在遍历j的过程中其实都计算过了。那么从1遍历j,比较(i - j) * j和dp[i - j] * j 取最大的。递推公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
也可以这么理解,j * (i - j) 是单纯的把整数拆分为两个数相乘,而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
所以递推公式:dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
那么在取最大值的时候,为什么还要比较dp[i]呢?
因为在递推公式推导的过程中,每次计算dp[i],取最大的而已。

(3)dp数组初始化
严格从dp[i]的定义来说,dp[0] dp[1] 就不应该初始化,也就是没有意义的数值。
拆分0和拆分1的最大乘积是多少?这是无解的。
这里我只初始化dp[2] = 1,从dp[i]的定义来说,拆分数字2,得到的最大乘积是1,这个没有任何异议!

(4)确定遍历顺序
确定遍历顺序,先来看看递归公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
dp[i] 是依靠 dp[i - j]的状态,所以遍历i一定是从前向后遍历,先有dp[i - j]再有dp[i]。

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

注意 枚举j的时候,是从1开始的。从0开始的话,那么让拆分一个数拆个0,求最大乘积就没有意义了。
j的结束条件是 j < i - 1 ,其实 j < i 也是可以的,不过可以节省一步,例如让j = i - 1,的话,其实在 j = 1的时候,这一步就已经拆出来了,重复计算,所以 j < i - 1
至于 i是从3开始,这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
更优化一步,可以这样:

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

因为拆分一个数n 使之乘积最大,那么一定是拆分成m个近似相同的子数相乘才是最大的。
例如 6 拆成 3 * 3, 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。
那么 j 遍历,只需要遍历到 n/2 就可以,后面就没有必要遍历了,一定不是最大值。

(5)举例推导dp数组
举例当n为10 的时候,dp数组里的数值,如下:
在这里插入图片描述

代码:

class Solution {
    public int integerBreak(int n) {
        int[]dp = new int[n+1];
        //dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            for(int j=1; j <= i/2;j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}


96.不同的二叉搜索树

题目链接:https://leetcode.cn/problems/unique-binary-search-trees/

思路:

dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
在这里插入图片描述
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
在这里插入图片描述
此时我们已经找到递推关系了,那么可以用动规五部曲再系统分析一遍。

动规五部曲:
(1)确定dp数组以及下标含义
dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]。

(2)确定递归公式
在上面的分析中,其实已经看出其递推关系, dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素,从1遍历到i为止。
所以递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量

(3)dp数组初始化
初始化,只需要初始化dp[0]就可以了,推导的基础,都是dp[0]。
从定义上来讲,空节点也是一棵二叉树,也是一棵二叉搜索树,这是可以说得通的。
从递归公式上来讲,dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0,也需要dp[以j为头结点左子树节点数量] = 1, 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1

(4)确定遍历顺序
首先一定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以看出,节点数为i的状态是依靠 i之前节点数的状态。
那么遍历i里面每一个数作为头结点的状态,用j来遍历。

(5)举例推导dp数组
举例当n为5的时候,dp table(dp数组)应该是这样的
在这里插入图片描述

代码:

class Solution {
    public int numTrees(int n) {
        int[]dp = new int[n+1];
        dp[0] = 1;
        for(int i=1 ;i<=n;i++){
            for(int j=1; j<=i ;j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }

        return dp[n];
    }
}

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

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

相关文章

tomcat 实现会话绑定

Tomcat 后端服务器实现 Session ID会话保持 基础架构&#xff1a; 7-6 代理服务器nginx配置 7-3 tomcat 服务器 7-5 同理 测试&#xff1a; 此时刷新&#xff0c;会话ID一直在变&#xff0c;这样不好 如何解决呢&#xff1f; 不好的是确定ip之后&#xff0c;会一直在一台机上…

AI对话/绘画完整系统(附完整源码,已开源)

文章目录 功能UI界面使用地址环境完整源码 功能 支持邮件激活账号&#xff0c;微信登录&#xff0c;短信登录支持上下文对话支持GPT4,claude3文件/图片分析分析&#xff0c;几乎所有模型均支持支持模糊匹配自定义回复消息支持按此按张按余额多种扣费方式支持套餐卡密生成及自定…

【C语言步行梯】各类操作符、类型转换与原码、反码、补码详谈

&#x1f3af;每日努力一点点&#xff0c;技术进步看得见 &#x1f3e0;专栏介绍&#xff1a;【C语言步行梯】专栏用于介绍C语言相关内容&#xff0c;每篇文章将通过图片代码片段网络相关题目的方式编写&#xff0c;欢迎订阅~~ 文章目录 算术运算符原码、反码、补码介绍移位运算…

C++11:自动类型推导 auto 和 decltype(下)

前面两篇文章分别介绍了 auto 和 decltype&#xff0c;今天聊聊它们两者之间的区别。 语法格式的区别 auto varname value; // auto的语法格式 decltype(exp) varname [ value]; // decltype的语法格式其中&#xff0c;varname 表示变量名&#xff0c;value 表示赋给变量的值…

如何有效地组织和管理自己的代码?

如何有效地组织和管理自己的代码&#xff1f; &#x1f9e9; &#x1f6e0;️ 如何有效地组织和管理自己的代码&#xff1f; &#x1f9e9;摘要引言正文1. 使用合适的目录结构2. 模块化设计3. 命名规范4. 版本控制 总结参考资料 博主 默语带您 Go to New World. ✍ 个人主页——…

L3-020 至多删三个字符(Python)

给定一个全部由小写英文字母组成的字符串&#xff0c;允许你至多删掉其中 3 个字符&#xff0c;结果可能有多少种不同的字符串&#xff1f; 输入格式&#xff1a; 输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 106] 内的字符串。 输出格式&#xff1a; 在一行…

Redis基础部分学习笔记

一、Redis的安装与配置 Redis是基于内存的&#xff0c;是单线程的。Redis可以用作数据库、缓存、消息中间件。 Redis一些常见的应用场景如下&#xff1a; &#xff08;1&#xff09;缓存 利用Redis快速的读写速度&#xff0c;可以将热点数据放入Redis中&#xff0c;应用从R…

零知识玩转AVH(7)—— 门槛任务(2)所遇错误及解决(1)

接前一篇文章&#xff1a;零知识玩转AVH&#xff08;6&#xff09;—— 门槛任务&#xff08;1&#xff09;源码下载、编译及运行 上一回说到完成门槛任务 https://github.com/ArmDeveloperEcosystem/Paddle-examples-for-AVH &#xff08;推荐&#xff0c;内含 ML 视觉用例&am…

前后端分离项目环境搭建

1. 使用到的技术和工具 springboot vue项目的搭建 工具 idea&#xff0c;mavennodejs 2. 后端框架搭建 利用maven创建springboot项目 3. 前端项目搭建 1. 安装相关工具 nodejs&#xff1a; 一个开源、跨平台的 JavaScript 运行时环境&#xff0c;可以理解成java当中需要…

企业微信 API 接口调用教程:深入解析企业微信 API 的用法

本文通过 access_token 凭证的方式来讲解怎么调用 企业微信 API&#xff0c;并一步步介绍如何获取企业微信 API 的 corpsecret、corpid、access_token 凭证以及怎么向企业微信的应用发送消息。 企业微信 API 在线地址为&#xff1a;qiyeweixin.apifox.cn/ &#xff0c;这个在线…

LInux 进程替换(理解系统调用)

目录 一、替换原理 二、替换函数 1、exec函数 2、命名理解 3、返回值 4、使用execl/lp、execv/vp 5、执行自定义命令 Makefile编译多个文件 命令行程序mycmd.c 传入自己的可执行文件 7、子进程都继承父进程环境变量 8、execle/ve修改子进程环境变量 9、exece函数为…

Hack The Box-Jab

目录 信息收集 nmap enum4linux 服务信息收集 Pidgin kerbrute hashcat 反弹shell & get user 提权 系统信息收集 端口转发 漏洞利用 get root 信息收集 nmap 端口探测┌──(root㉿ru)-[~/kali/hackthebox] └─# nmap -p- 10.10.11.4 --min-rate 10000 -oA…

Docker----Dockerfile构建微服务镜像

目录 一、关键步骤 二、具体步骤 1、准备后端jar包(这里以java后端演示) 2、编写Dockerfile 3、构建镜像 4、运行镜像容器 5、测试是否成功 一、关键步骤 1、准备后端jar包(这里以java后端演示) 2、编写Dockerfile 3、构建镜像 4、运行镜像容器 5、测试是否成功 二…

Openfeign使用教程(带你快速体验Openfeign的便捷)

文章摘要 本文中将教会您如何快速使用Openfeign&#xff0c;包括Opengfeign的基础配置、接口调用、接口重试、拦截器实现、记录接口日志信息到数据库 文章目录 文章摘要一、Openfeign初步定义二、Openfeign快速入门1.引入maven坐标2.启动类增加EnableFeignClients注解3.定义fei…

从金蝶云星空到钉钉通过接口配置打通数据

从金蝶云星空到钉钉通过接口配置打通数据 对接系统金蝶云星空 金蝶K/3Cloud&#xff08;金蝶云星空&#xff09;是移动互联网时代的新型ERP&#xff0c;是基于WEB2.0与云技术的新时代企业管理服务平台。金蝶K/3Cloud围绕着“生态、人人、体验”&#xff0c;旨在帮助企业打造面…

IDEA连接Mysql失败:下载驱动失败,Failed todownload Cannot download Read timed out

解决&#xff1a; 1. 手动加入jar包 2.选择自己maven仓库中存在mysql-connector 3. 选择完毕后&#xff0c;确定使用&#xff1a; 4. 进行测试连接

【代码随想录】【回溯算法】补day24:组合问题以及组合的优化

回溯算法&#xff1a;递归函数里面嵌套着for循环 给定两个整数 n 和 k&#xff0c;返回 1 … n 中所有可能的 k 个数的组合。 示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 包含组合问题和组合问题的剪枝优化 class solution:def combine(se…

免费接口调用 招标信息自动抽取|招标信息|招标数据解析接口

一、开源项目介绍 一款多模态AI能力引擎&#xff0c;专注于提供自然语言处理&#xff08;NLP&#xff09;、情感分析、实体识别、图像识别与分类、OCR识别和语音识别等接口服务。该平台功能强大&#xff0c;支持本地化部署&#xff0c;并鼓励用户体验和开发者共同完善&#xf…

git:码云仓库提交以及Spring项目创建

git&#xff1a;码云仓库提交 1 前言 码云访问稳定性优于github&#xff0c;首先准备好码云的账户&#xff1a; 官网下载GIT&#xff0c;打开git bash&#xff1a; 查看当前用户的所有GIT仓库&#xff0c;需要查看全局的配置信息&#xff0c;使用如下命令&#xff1a; git …

旅游管理系统 |基于springboot框架+ Mysql+Java+Tomcat的旅游管理系统设计与实现(可运行源码+数据库+设计文档)

推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 前台功能效果图 管理员功能登录前台功能效果图 系统功能设计 数据库E-R图设计 lunwen参考 摘要 研究…