代码编织梦想

343. 整数拆分

题目链接:力扣

思路

        动态规划的题目虽然说是要先确定dp数组的含义,再确定递归公式,但是总感觉这两者是相辅相成的,是一起出来的,但是到此,dp数组代表的都是我们要求取的值

1、确定dp数组以及下标的含义

        i 代表dp数组的下标和 要被拆分的数字
        dp[i] 代表数字 i ,被拆分后相乘可以得到的最大值

2、确定递推公式

        获取递归公式要推导清楚,dp[i] 是怎么来的

        比如,现在的数字是10,进行拆分
        【1,9】【2,8】【3,7】【4,6】【5,5】后面的都会和前面重复,所以拆到5就可以了
        那么其实从 1 遍历,就可以获得dp[i] 可以通过 j * (i - j)进行获取

        还有就是后面得到的这个数组还可以进行拆分,比如【9、8、7、6、5】,这里就可以借助dp[]数组前面的元素了【9的拆分、8的拆分、7的拆分、6的拆分、5的拆分】,其实就是dp[9]、dp[8]、dp[7]……加一句:从这里也可以看到一点就是,遍历顺序应该是从前先后的,因为后面的拆分要使用前面数字的结果
        所以dp[i] 还可以通过 j * dp[i - j]进行获取

        总的来说 dp[i] = Math.max(dp[i] , j * (i - j) , j * dp[i - j]);

3、dp数组初始化

        对于初始化数组来说,dp[0],dp[1] 严格意义上来说,0 和 1 是不可拆分的,他们拆分后的最大值是不存在的

        2是可以进行拆分成 1 和 1 的。所以赋值为1

4、确定遍历顺序

        从前向后遍历

        其中的 j 其实最大值为 i-j ,再大只不过是重复而已
        并且本题中的 dp[0] , dp[1] 都是无意义的,j 最大值到达 i-j 。就不会用到 dp[0] 和 dp[1]

         j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
         而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘

5、打印dp数组

 

整数拆分

class Solution {
    public int integerBreak(int n) {

        // 创建dp数组
        int[] dp = new int[n + 1];

        // 初始化数组
        dp[2] = 1;

        // 填充dp[]数组
        for (int i = 3; i <= n; i++) {
            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.不同的二叉搜索树

题目链接:力扣

思路

        这道题目发现递推公式真的是太难了

1、定义dp[] 数组

        dp[i] 代表,由 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[0]就可以了,推导的基础,都是dp[0]
        初始化dp[0] = 1

4、遍历顺序

        从小到大遍历

5、打印dp数组

不同的二叉搜索树

class Solution {
    public int numTrees(int n) {

        // 定义dp[]数组
        int[] dp = new int[n + 1];

        // 初始化dp数组
        dp[0] = 1;
        
        // 填充dp数组
        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];
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_62575233/article/details/127958766

leetcode分类刷题-爱代码爱编程

二分查找 33. 搜索旋转排序数组d 递归 234. 回文链表 并查集 剑指 Offer II 116. 省份数量 拓扑排序 207. 课程表   二叉树 二叉树的遍历:深度优先 广度优先 递归 栈  队列 144. 二叉树的前序遍历 94. 二叉树的中序遍历 145. 二叉树的后序遍历 102. 二叉树的层序遍历

【代码随想录】【LeetCode】自学笔记 11 - 动态规划-爱代码爱编程

DP简介 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的 大家知道动规是由前一个状态推导出来的,而贪心是局部直接选最优的,对于刷题来说就够用了。 对于动态规划问题,我

Leetcode刷题笔记(代码随想录)-爱代码爱编程

1 数组  1.1 二分查找 第一种写法:我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] 。区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下三点: while (left <= right) 要使用 <= ,因为left == right是有

代码随想录1刷—动态规划篇(一)_97marcus的博客-爱代码爱编程

代码随想录1刷—动态规划篇(一) 动态规划基础理论步骤[509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)动态规划解法优化递归解法[70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/)拓展:完全背包问题[746. 使用最小花

代码随想录刷题记录:dp系列_pin_boy的博客-爱代码爱编程

代码随想录DP系列 53. 最大子数组和 考虑每个数组的尾部 dp[i] 代表 [0,i]位置上的最大子数组和, dp[i] = max(dp[i-1]+arr[i] , arr[i] ); // 选择加入之前的数组

代码随想录算法训练营第四十天| leetcode343. 整数拆分 96.不同的二叉搜索树_冰冰的coco的博客-爱代码爱编程

343. 整数拆分 题目:力扣 class Solution { public: int integerBreak(int n) { vector<int> dp(n+1); dp[2] = 1; for(int i = 3; i<= n; ++i){

代码随想录训练营day44:1.不同路径ii、2.整数拆分、3.不同的二叉搜索树。_minixiaoxiaozhu的博客-爱代码爱编程

1.不同路径ii:代码随想录         1.疑问为啥在遇到障碍物之后坐标(i,0)之后的值全部是0?后来审题的时候才发现,机器人只能从上往下或者往右移一步,不能向上移动,故若障物在(i,0)之后全部都是“0”。         2.不要把dp的二维数组和题目中给出的obstaclegrid地图混为一谈,dp数组是重新构建的数组,相当于是根

leetcode动态规划算法总结——更新_依嘫_吃代码的博客-爱代码爱编程

系列文章目录 文章目录 系列文章目录前言基础类一、 509. 斐波那契数二、leetcode [70. 爬楼梯-java实现](https://blog.csdn.net/qq_41810415/article

代码随想录day41|动态规划 343. 整数拆分 96.不同的二叉搜索树_$wavy的博客-爱代码爱编程

目录 题目:343.整数拆分 题目链接:https://leetcode.cn/problems/integer-break/ 题目:96.不同的二叉搜索树 题目链接:https://leetcode.cn/problems/unique-binary-search-trees/ 题目:343.整数拆分 题目链接:https://leet

代码随想录刷题day41 | 343. 整数拆分 | 96. 不同的二叉搜索树_dum1615的博客-爱代码爱编程

代码随想录刷题Day41 | 343. 整数拆分 | 96. 不同的二叉搜索树 343. 整数拆分 题目: 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

代码随想录算法训练营第四十一天| leetcode343. 整数拆分、leetcode96. 不同的二叉搜索树_喵的博客-爱代码爱编程

一、LeetCode343. 整数拆分         1:题目描述(343. 整数拆分)         给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。         返回 你可以获得的最大乘积 。         2:解题思路         动态规划         动规

代码随想录第四十一天|343.整数拆分,96.不同的二叉搜索树_baozu的博客-爱代码爱编程

343. 整数拆分 - 力扣(Leetcode) dp含义,拆分需要想一想 class Solution { public: int integerBreak(int n) { vector<int>dp(n+1); dp[2]=1; for(int i=3;i<=n;i++)

动态规划 | 不同路径、整数拆分、不同的二叉搜索树 | leecode刷题笔记-爱代码爱编程

文章目录 62. `中等`不同路径题目分析完整代码如下 63. 不同路径 II题目分析——`有障碍物`完整代码如下 343. 整数拆分题目分析完整代码如下 96. `困难`不同的二叉搜索树题目

leetcode(c++)-爱代码爱编程

746. 使用最小花费爬楼梯 代码: class solution { //746. 使用最小花费爬楼梯 //1. 确定dp数组以及下标的含义:dp[i]到达第i个台阶的最少花费 //2. 确定递推公式:dp[i]=

代码随想录day41|343. 整数拆分|96.不同的二叉搜索树|golang_整数拆分 代码随想录-爱代码爱编程

代码随想录day41 目录 代码随想录day41 343. 整数拆分 96.不同的二叉搜索树 343. 整数拆分 思路         看到这道题目,都会想拆成两个呢,还是三个呢,还是四个....。我们来看一下如何使用动规来解决 动态规划 动规五部曲,分析如下: 1、确定dp数组(dp table)以及下标的含义:      

leetcode刷题day41|343.整数拆分、96.不同的二叉搜索树-爱代码爱编程

文章目录 一、343.整数拆分二、96.不同的二叉搜索树1. 递归方式2.非递归方式 一、343.整数拆分 注意的点: 递推公式是寻找 分成2个数 和 分成3个及以上数 这两种情况的最大值。

代码随想录算法训练营day41 | 343. 整数拆分,96. 不同的二叉搜索树-爱代码爱编程

343. 整数拆分 第一想法是将2和3的情况作为base condition,因为要想得到最大的乘积,就需要最终拆分成一个或多个2和3,例如n=10的情况需要拆分成2+2+3+3。但是看完题解发现,首先这个思路符合的是贪心的思路,其次要注意的是拆分成多个3和一个小于4的数(之前也想到了4,但是觉得4依旧可以拆成2+2,但是同样是n=10,如果比较n&g

算法训练 day41 | 动态规划训练day3;leetcode343. 整数拆分;leetcode96. 不同的二叉搜索树-爱代码爱编程

目录 LeetCode343. 整数拆分 1. 思路 2. 代码实现 3. 复杂度分析 4. 思考与收获 LeetCode96. 不同的二叉搜索树  1. 思路 2. 代码实现 3. 复杂度分析 4. 思考与收获 LeetCode343. 整数拆分 链接:343. 整数拆分 - 力扣(LeetCode) 1. 思路 看到

35.动态规划(3) | 整数拆分(h)、不同的二叉搜索树(h)-爱代码爱编程

        今天的2道题都没有自己做出来,感觉比较难想到解法,但解法本身并不复杂。这2道题的重点都在状态转移方程。它们不再依赖于前一两个或者前一行的某个数字,而是依赖于之前所有的dp值。每求一个dp数值时,都需要进行内层循环,或是在内层循环中取一个最大值,或是把循环中的某个结果值都相加。感觉重点是要把问题分成若干情况来讨论,并且让每种情况能对应到