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

本文主要是介绍代码随想录算法训练营第四十一天| 343. 整数拆分,96.不同的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目与题解

343. 整数拆分

题目链接:343. 整数拆分

代码随想录题解:343. 整数拆分

视频讲解:动态规划,本题关键在于理解递推公式!| LeetCode:343. 整数拆分_哔哩哔哩_bilibili

解题思路:

        一眼懵,直接看答案了

看完代码随想录之后的想法 

        前一天的题是由dp[i-2]和dp[i-1],递推出当前结果dp[i]。这题更复杂一些,是要根据dp[0]到dp[i-1],推算dp[i]的结果。

        对于数字i,可以分解为两个数字的和:j和i-j,因此求分解i的乘积,就是求j和分解i-j之后二者的乘积。那么如果dp[i]定义为数字i的最大乘积和,那么对于dp[i],遍历j from 1 to i - 1, 递推公式为求dp[i-j]*j和j * (i - j) 中的最大值。

        为避免重复计算,j最多取到i的一半。

class Solution {public int integerBreak(int n) {int[] dp = new int[n+1];if (n >= 2) 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), dp[i-j]*j));}}return dp[n];}
}

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 - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。

所以递推公式:dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

 还需要注意,初始化的方式是跟着定义走的,如果求的是max(dp[i - j] * dp[j]),为了计算正确,初始化的结果会跟dp[i]定义不符,容易出错。

遇到的困难

        第一次碰到这种题,想不到

96.不同的二叉搜索树 

题目链接:96.不同的二叉搜索树 

代码随想录题解:​​​​​​​96.不同的二叉搜索树 

视频讲解:动态规划找到子状态之间的关系很重要!| LeetCode:96.不同的二叉搜索树_哔哩哔哩_bilibili

解题思路:

        这题跟上面一题有一点类似,同样是要用多个dp[i-j]的值推出dp[i]。

        题目要求用1-n的数字构成不同的二叉搜索树,其实可以分解为,0-j-1的数字构成左子树,j为根节点,j到i构成右子树,那么

dp[i] = \sum_{1}^{i}dp[j-1]*dp[i-j]

        初始化dp[0]=dp[1]=0即可。

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

看完代码随想录之后的想法 

        以dp[3]为例

dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

关键是看如何去分解,分解后如何正确确定遍历的上下限。

遇到的困难

        一开始写的时候没有想清楚遍历的边界,初始化的时候也有点糊涂,所以错了好几处。要记住按定义初始化dp,然后确定遍历上下界后,最好通过几个举例得到结果,保证边界正确。        

今日收获

        学会了如何用分解的方法使用dp,难度提升了很多。

这篇关于代码随想录算法训练营第四十一天| 343. 整数拆分,96.不同的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到