Day 41:动态规划 LeedCode 343. 整数拆分 96.不同的二叉搜索树

343. 整数拆分

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

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

思路:

1.确定dp数组(dp table)以及下标的含义

dp[i]分拆数字i,可以得到的最大乘积为dp[i]。

2.确定递推公式

dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

j*(i-j):拆分成两个数之间相乘

j*dp[i-j]:拆分成两个及两个以上

为什么j不拆分?

从1遍历到j,相当于j已经被拆分过了

3.dp数组如何初始化

dp[2]=1:2拆分成1*1=1

0,1无法拆分,不对dp[0],dp[1]初始化

所以后面我们遍历时需要满足i-j>=2

4.确定遍历顺序

dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

由地推公式可知,从左往右遍历

5.举例推导dp数组

代码:

class Solution {
    public int integerBreak(int n) {
  int[] dp=new int[n+1];
  dp[2]=1;
  //计算得出dp数组中所有值
  for(int i=2;i<=n;i++){
    //将 i拆分成j,i-j
  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];
    }
}

代码优化:

如图可见i可以分成1*2, 1*1*1, 2*1其中1*2和2*1其实是重复了

所以我们拆分时,让i<=i-j,即左边的数小于等于右边

class Solution {
    public int integerBreak(int n) {
  int[] dp=new int[n+1];
  dp[2]=1;
  //计算得出dp数组中所有值
  for(int i=3;i<=n;i++){
    //将 i拆分成j,i-j
  for(int j=1;j<=i-j;j++){
    dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
  }
  }
    return dp[n];
    }
}

96. 不同的二叉搜索树

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

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

思路:

由图可知

当n=3时:

头结点为1,左子结点个数为0,右子节点个数为2  

头结点为2,左子结点个数为1,右子节点个数为1  

头结点为3,左子结点个数为2,右子节点个数为0  

 1.确定dp数组(dp table)以及下标的含义

dp[i]表示有i个结点时,有多少不互相同的二叉树

2.确定递推公式

如图

dp[3]=d[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]

故dp[i]+=dp[j-1]*dp[i-j]

j-1:左子结点个数

i-j:右子节点个数

3.dp数组如何初始化

dp[0]=1;

4.确定遍历顺序

由dp[i]+=dp[j-1]*dp[i-j]可知:dp[i]是根据之前状态得到的

5.举例推导dp数组

class Solution {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
     for(int i=1;i<=n;i++){
//将i个结点划分成不同左右结点的情况
    for(int j=1;j<=i;j++){
        dp[i]+=dp[i-j]*dp[j-1];
    }

     }
     return dp[n];
    }
}

 

 

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

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

相关文章

支付系统核心逻辑 — — 状态机(JavaGolang版本)

支付系统核心逻辑 — — 状态机 代码地址&#xff1a;https://github.com/ziyifast/ziyifast-code_instruction/tree/main/state_machine_demo 1 概念&#xff1a;FSM&#xff08;有限状态机&#xff09;&#xff0c;模式之间转换 状态机&#xff0c;也叫有限状态机&#xff08…

OpenWrt 多拨负载均衡不起作用

检查 负载均衡->规则->Https->粘滞模式 是否启动&#xff0c;设置为 否 如果设置为是&#xff0c;那么根据官方描述&#xff1a; 来自相同源 IP 的流量&#xff0c;如果已经匹配过此规则并且在粘滞超时时间内&#xff0c;将会使用相同的 WAN 接口 意思就是如果你同一个…

R语言 并行计算makeCluster报错

问题&#xff1a;使用parallel包进行并行计算&#xff0c; cl <- makeCluster(detectCores()) 出现以下问题&#xff1a; 解决方式&#xff1a;用makeClusterPSOCK命令代替即可 library("future") cl <- makeClusterPSOCK(124, revtunnel TRUE, outfile &…

【QT入门】Qt自定义控件与样式设计之自定义QTabWidget实现tab在左,文本水平的效果

往期回顾 【QT入门】Qt自定义控件与样式设计之控件提升与自定义控件-CSDN博客 【QT入门】Qt自定义控件与样式设计之鼠标相对、绝对位置、窗口位置、控件位置-CSDN博客【QT入门】Qt自定义控件与样式设计之自定义QLineEdit实现搜索编辑框-CSDN博客 【QT入门】Qt自定义控件与样式…

(一)基于IDEA的JAVA基础16(end)

二维数组 二维数组就是数组里面再放一个数组 语法: <数据类型> [] [] 数组名&#xff1b; 或: <数据类型> 数组名 [] []&#xff1b; 比如这里有5个单位&#xff0c;每个单位员工有20个&#xff0c;他们都在忙几个相同的项目&#xff0c;现在要对某项项目进行操…

html、css、QQ音乐移动端静态页面,资源免费分享,可作为参考,提供InsCode在线运行演示

CSDN将我上传的免费资源私自变成VIP专享资源&#xff0c;且作为作者的我不可修改为免费资源&#xff0c;不可删除&#xff0c;寻找客服无果&#xff0c;很愤怒&#xff0c;&#xff08;我发布免费资源就是希望大家能免费一起用、一起学习&#xff09;&#xff0c;接下来继续寻找…

Linux进阶篇:centos7搭建jdk环境

Linux服务搭建篇&#xff1a;centos7搭建jdk环境 本文主要介绍的是如何是Linux环境下安装JDK的&#xff0c;关于jdk的概念就不做赘述了&#xff0c;相信大家都有所耳闻了&#xff0c;Linux环境下&#xff0c;很多时候也离不开Java的&#xff0c;下面笔者就和大家一起分享如何jd…

【数据结构|C语言版】单链表应用

前言1. 基于单链表实现通讯录1.1 知识要求1.2 功能要求 2. 代码总结2.1 SeqList.h2.2 SeqList.c2.3 Contact.h2.4 Contact.c2.5 test.c 后言 上期回顾&#xff1a;【数据结构|C语言版】单链表 前言 各位小伙伴大家好&#xff01;上期小编讲解了单链表相关知识&#xff0c;在此…

SpringCloudAlibaba真的不行了吗?

Spring Cloud Alibaba 作为SpringCloudAlibaba微服务架构实战派上下册和RocketMQ消息中间件实战派上下册的作者胡弦&#xff0c;我想和技术人聊一下&#xff0c;阿里巴巴开源的SpringCloudAlibaba真的不行了吗&#xff1f; 目前SpringCloudAlibaba最新的版本为2023.0.0.0-RC1 …

蓝桥杯2024年第十五届省赛

E:宝石组合 根据给的公式化简后变为gcd(a,b,c)根据算数基本定理&#xff0c;推一下就可以了 然后我们对1到mx的树求约数&#xff0c;并记录约数的次数&#xff0c;我们选择一个最大的且次数大于等3的就是gcd int mx; vector<int> g[N]; vector<int> cnt[N]; int…

flutter material中的Icon组件的IconData 查阅

查阅 https://fonts.google.com/icons?selectedMaterialSymbolsOutlined:expand_less:FILL0;wght300;GRAD0;opsz24&icon.platformandroidhttps://fonts.google.com/icons?selectedMaterialSymbolsOutlined:expand_less:FILL0;wght300;GRAD0;opsz24&icon.platformand…

Java的maven项目导入本地jar包的三种方式

一、使用本地jar包 在项目中创建一个lib文件夹&#xff0c;将想要使用的本地jar包放进去 然后直接在pom.xml中添加下列依赖&#xff08;项目协作推荐&#xff09; <dependency><groupId>com.fpl</groupId><artifactId>spring</artifactId><…

Linux下SPI设备驱动实验:验证SPI节点及ICM20608设备子节点

一. 简介 前一篇文章在设备树文件中创建了SPI的 IO 的 pinctrl节点&#xff0c;SPI节点及ICM20608设备子节点&#xff0c;文章如下&#xff1a; Linux下SPI设备驱动实验&#xff1a;创建SPI节点及SPI设备子节点-CSDN博客 本文对设备树文件进行加载测试&#xff0c;确定SPI节…

leetcode199 二叉树的右视图

题目 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 示例 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 解析 这道题首先能想到的办法&#xff0c;就是使用迭代法层次遍历&…

部署项目的时候的一些错误

项目打jar包&#xff0c;找不到资源&#xff0c;连接不上数据库 项目打包后无法运行 直接在idea运行可以 解决方法&#xff1a;pom文件中增加&#xff08;配置文件如果是yml&#xff0c;写yml&#xff09; <resources><resource><directory>src/main/java&…

系统学c#:2、基础语法(关键字、标识符、数据类型、变量、常量、字面量、运算符、类型转换)

关键字&#xff1a; 关键字是编程语言中具有特殊含义的单词或符号&#xff0c;它们通常被编程语言用于表示特定的语法结构、操作或约定。在C#中&#xff0c;关键字具有特定的语法和功能&#xff0c;用于定义语言的基本结构和规则。 以下是一些C#中常用的关键字及其功能&#xf…

【计算机毕业设计】游戏售卖网站——后附源码

&#x1f389;**欢迎来到琛哥的技术世界&#xff01;**&#x1f389; &#x1f4d8; 博主小档案&#xff1a; 琛哥&#xff0c;一名来自世界500强的资深程序猿&#xff0c;毕业于国内知名985高校。 &#x1f527; 技术专长&#xff1a; 琛哥在深度学习任务中展现出卓越的能力&a…

MybatisPlus——自定义Sql

MybatisPlus——自定义Sql 自定义sql mybatisplus自定义sql并不是全部进行自定义的&#xff0c;我们可以利用MybatisPlus的Wrapper来构建复杂的Where条件&#xff0c;然后自己定义sql语句中剩下的部分。 自定义sql案例 以为例&#xff1a;将id在指定范围&#xff08;1&…

搜索树, 哈希表

目录 一. 搜索树 1.1 概念 1.2 操作1 查找 1.3 操作2 插入 1.4 操作3 删除 1.5 性能分析 1.6 和 java 类集的关系 二.哈希表 2.1 概念 2.2 哈希冲突 2.3常见哈希函数 2.4 负载因子 2.5 闭散列 2.6 开散列 2.7 哈希表的实现 push 添加数据 getVal() 获取key对应的v…

SQL注入sqli_labs靶场第十七题

B站教学视频很详细 【sql注入之sqli-labs系列教程(less11-17)】sqli-labs_33_less17_哔哩哔哩_bilibili 我将SQL语句在页面中显示&#xff0c;以便更深入学习。 1.寻找注入点 修改密码的一个页面。 输入正确的账号密码&#xff0c;可以看到&#xff0c;账号为admin&#xf…