LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

这篇具有很好参考价值的文章主要介绍了LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、LeetCode343. 整数拆分

题目链接:343. 整数拆分
题目描述:

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

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

示例 1:

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

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58
算法分析:
定义dp数组及下标含义:

dp[i]表述正整数i拆分成k个正整数乘积所能够得到的最大值。

递推公式:

用一个j来遍历从1到i,得到两个dp[i],即dp[i]=j*(i-j)(将整数i分成两个正整数j和i-j),和dp[i]=j*dp[i-j]。

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

初始化:

dp[0]和dp[1]初始化没有意义,所以我们初始化dp[2]=1(2拆分成两个1相乘)。

遍历顺序:

因为dp[2]已经初始化了,所以我们从3遍历到n。

代码如下:

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 * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

时间复杂度o(n^2),空间复杂度o(n)。

二、LeetCode96. 不同的二叉搜索树

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

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

示例 1:

LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树,算法,leetcode,动态规划,java

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 19
算法分析:
定义dp数组及下标含义:

dp[i]表示i个节点组成的二叉搜索树的种树。

递推公式:

j从1遍历到i,当j为头节点时,左子树有i-1个节点,左子树的种类数相当于dp[j-1],右子树有i-j个节点,右子树的种类数相当于dp[i-j]。

所以dp[i]+=dp[j-1]*dp[i-j],j从1比那里遍历到i;

初始化:

dp[0]初始化为1(0的话会影响乘法结果),dp[1]初始化为1(一个节点的二叉搜索树只有一种情况)

遍历顺序:

i从2遍历到n,然后确定dp[i](dp[i]+=dp[j-1]*dp[i-j])。

如果结果有误打印dp数组检查验证。

代码如下:

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

时间复杂度o(n^2),空间复杂度o(n)

总结

这两道题还是比较难的,自己想很难有思路。文章来源地址https://www.toymoban.com/news/detail-761482.html

到了这里,关于LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣】343. 整数拆分 <动态规划、数学>

    给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k = 2 ),并使这些整数的乘积最大化。返回可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 动态规划 确定 dp 数组以及下

    2024年02月09日
    浏览(42)
  • 算法训练第四十一天|343. 整数拆分 、96.不同的二叉搜索树

    题目链接:343. 整数拆分 参考:https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html 题目描述 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入:

    2023年04月24日
    浏览(44)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(52)
  • 算法刷刷刷|动态规划篇|509.斐波那契数| 70.爬楼梯| 746.使用最小花费爬楼梯| 62.不同路径| 63不同路径2| 343.正数拆分 | 96.不同的二叉搜索树

    509. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 70.爬楼梯 746.使用最小花费爬楼梯 给你一个整数

    2023年04月23日
    浏览(56)
  • 我在代码随想录|写代码Day33 | 动态规划| 路径问题| 62.不同路径,63. 不同路径 II,343. 整数拆分

    🔥博客介绍`: 27dCnc 🎥系列专栏: 数据结构与算法 算法入门 C++项目 🎥 当前专栏: 算法入门 专题 : 数据结构帮助小白快速入门算法 👍👍👍👍👍👍👍👍👍👍👍👍 ☆*: .。. o(≧▽≦)o .。.:*☆ ❤️感谢大家点赞👍收藏⭐评论✍️ 今日学习打卡 代码随想录 - 动态规划

    2024年03月11日
    浏览(62)
  • 代码随想录Leetcode 343. 整数拆分

            dp[i]表示i所能拆分的最大乘积,则dp[i] 与dp[i - 1]的递推公式是:                 max( 1~n * dp[n ~ 1])

    2024年02月21日
    浏览(85)
  • 343. 整数拆分

    343. 整数拆分 https://leetcode.cn/problems/integer-break/description/ 贴一张对比数据图,大家可以自行验证,是否上述规律会得到正确答案。

    2024年02月14日
    浏览(44)
  • Leetcode题解-算法-动态规划(python版)

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种,1、先走 1 级台阶,再走 n-1 级台阶;2、先走 2 级台阶,再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(50)
  • 整数拆分(力扣)动态规划 JAVA

    给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k = 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 里程碑意义 解题思路:

    2024年02月17日
    浏览(46)
  • 【力扣刷题】整数拆分(动态规划)

    个人简历: 全栈领域新星博主, 万粉博主、 帮助初学者入门,记录自己的学习过程 个人主页:天寒雨落的博客_CSDN博客-C,CSDN竞赛,python领域博主 热门专栏:初学者入门C语言_天寒雨落的博客-CSDN博客   目录 动态规划 整数拆分 题目 思路 代码 执行结果 其基本思想是将待求解

    2024年02月03日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包