Leetcoder Day36| 动态规划part03

2024-03-04 08:28

本文主要是介绍Leetcoder Day36| 动态规划part03,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

343. 整数拆分

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

  • 输入: 2
  • 输出: 1
  • 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

  • 输入: 10
  • 输出: 36
  • 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
  • 说明: 你可以假设 n 不小于 2 且不大于 58。

本题需要注意的是,至少拆成2个正整数的和,而不是正好是2个正整数。

  1. 确定dp数组以及下标的含义:dp[i]为整数i拆分后的最大乘积
  2. 确定递推公式:假如将i拆分为j和i-j,这里j不只是代表一个数字而是一可能由j个整数组成的乘积。如果从1遍历到j,有两种途径可以得到dp[i],一个是dp[i]=j*(i-j),另一个是dp[i]=j*dp[i-j],这里dp[i-j]代表i-j这个数字被拆分后的最大值。
  3. dp数组如何初始化:本题将i拆成0是没有意义的,所以不考虑,1拆开只能是1和0,也是没有意义的,所以从2开始初始化,2可以拆成1 + 1,因此dp[2]=1
  4. 确定遍历顺序:既然初始化是从2开始的,所以i从3开始遍历,j从1开始遍历,到i停止。
  5. 举例推导dp数组:没法通过简单计算举例。
class Solution {public int integerBreak(int n) {int[] dp=new int[n+1]; dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<i;j++){dp[i]=Math.max(dp[i], Math.max(j*dp[i-j], j*(i-j)));}}return dp[n];}
}

⚠️本题的优化思路:其实将对于j的遍历条件改为: j<i-1可以节省一步计算,因为如果让j=i-1,其实在 j = 1的时候,这一步就已经拆出来了,属于重复计算,所以 j < i - 1。

更优化一步,可以这样:

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));}
}

因为拆分一个数i使之乘积最大,比如i=x+(i-x) dp[i]=x(i-x)=xi-x^2,这时是一个向下的抛物线,最大点为x/2

96.不同的叉搜索树

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

示例:

这道题要求能构造多少二叉搜索树。二叉搜索树是有一定规律的,其中序遍历是有序的。按照示例所给,可以先从1开始遍历,看以i为根节点能构造出多少子树。其实一开始还是没有什么思路,主要是递推公式不太好想,所以准备按照五部曲依次思考一下:

  1. 确定dp数组以及下标的含义:dp[i]为有i个节点时能构造的二叉搜索树个数。
  2. 确定递推公式:目前还没有什么思路。
  3. dp数组如何初始化:若n=1,则dp[1]毫无疑问是1,若n=2,则有两种构造方法,一种是以1为根节点,左子树为空,右子树为2;一种是以2为根节点,左子树为1,右子树为空,所以dp[2]=2;n=3就是示例中所给情况,可以看到,如果以1为根节点,则左子树一定为空的,右子树有两种可能,分别是以2和3为子树根节点。若以2为根节点,则左右子树各有一个节点,有一种可能,若以3为根节点,则右子树为空,左子树有两种可能,分别是以1和2为子树根节点。

当分析到如何初始化的时候,已经渐渐有了关于推导递推公式的雏形,接下来可以捋一下思路:

当n=1时:只有一个节点,不附图了

当n=2时:如下

当n=3时,有三种大的情况:

  1. 以1为根节点:因为此题本质求的是树的形状的可能性,所以跟具体的数值关系不大,如果把1去掉来看,可以看到,其实剩下的形状和n=2的时候是一样的:
  2. 以2为根节点:左边节点1,右边节点3
  3. 以3为根节点:去掉3,剩下的形状和n=2的时候也是一样的:

因此

  • 有2个元素的搜索树数量就是dp[2]。
  • 有1个元素的搜索树数量就是dp[1]。
  • 有0个元素的搜索树数量就是dp[0]。

可以这样推导:

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

那么n=3时,dp[3]就是上面三种情况的搜索树个数之和,即dp[3]=dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2] ,

拓展到i就是:不断地累加:dp[以j为头结点左子树节点数量]*dp[以j为头结点右子树节点数量],j的范围为[1, i]

所以递推公式为:dp[i]+=dp[j-1]*dp[i-j],因此下面完整的五部曲为:

  1. 确定dp数组以及下标的含义:有i个节点时能构造的二叉搜索树个数
  2. 确定递推公式:dp[i]+=dp[j-1]*dp[i-j]
  3. dp数组如何初始化:要注意,从定义上来讲,空节点也是一棵二叉树,也是一棵二叉搜索树,所以dp[0]=1,这个我一开始弄错了。dp[1]=1
  4. 确定遍历顺序:i从1到n,j从1到i
  5. 举例推导dp数组:无法手动举更多例子
class Solution {/**确定dp数组以及下标的含义:有i个节点时能构造的二叉搜索树个数确定递推公式:dp[i]+=dp[j-1]*dp[i-j]dp数组如何初始化:dp[1]=1,dp[2]=2确定遍历顺序:i从3到n,j从1到i*/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];}
}

这篇关于Leetcoder Day36| 动态规划part03的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后