郑州网站建设廴汉狮网络,网站建设开发软件有哪些方面,常见制作网页的软件,世界知名设计公司名称343. 整数拆分 题目链接#xff1a;整数拆分 题目描述#xff1a; 给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 解题思路#xff1a; 1、确定dp数组…343. 整数拆分 题目链接整数拆分 题目描述 给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 解题思路 1、确定dp数组dp table以及下标的含义 设置dp[i] 为i的拆分最大值 2、确定递推公式 dp[i] max(dp[i], max((i - j) * j, dp[i - j] *j)); 前一部分为将i分为i-j和j两部分后一部分是将i分为j和更多的分块的i-j。 3、dp数组如何初始化 按照定义可以知道只有dp[2]有意义为1 4、确定遍历顺序 dp[i] 是依靠 dp[i - j]的状态所以遍历i一定是从前向后遍历先有dp[i - j]再有dp[i]。 5、举例推导dp数组
代码实现
class Solution {public int integerBreak(int n) {int[] dp new int[n1];dp[2] 1;for(int i 3;in;i){for(int j 1; ji-j;j){dp[i] Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));System.out.println(dp[i]);}}return dp[n];}
}96. 不同的二叉搜索树 题目链接不同的二叉搜索树 题目描述 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 解题思路 本题主要的难点在于递推过程的理解借用卡哥的解释
当1为头结点的时候其右子树有两个节点看这两个节点的布局是不是和 n 为2的时候两棵树的布局是一样的啊 可能有同学问了这布局不一样啊节点数值都不一样。别忘了我们就是求不同树的数量并不用把搜索树都列出来所以不用关心其具体数值的差异 当3为头结点的时候其左子树有两个节点看这两个节点的布局是不是和n为2的时候两棵树的布局也是一样的啊 当2为头结点的时候其左右子树都只有一个节点布局是不是和n为1的时候只有一棵树的布局也是一样的啊 发现到这里其实我们就找到了重叠子问题了其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。 思考到这里这道题目就有眉目了。 dp[3]就是 元素1为头结点搜索树的数量 元素2为头结点搜索树的数量 元素3为头结点搜索树的数量 元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量 元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量 元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量 有2个元素的搜索树数量就是dp[2]。 有1个元素的搜索树数量就是dp[1]。 有0个元素的搜索树数量就是dp[0]。 所以dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2] 代码实现
class Solution {public int numTrees(int n) {//初始化 dp 数组int[] dp new int[n 1];//初始化0个节点和1个节点的情况dp[0] 1;dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {//对于第i个节点需要考虑1作为根节点直到i作为根节点的情况所以需要累加//一共i个节点对于根节点j时,左子树的节点个数为j-1右子树的节点个数为i-jdp[i] dp[j - 1] * dp[i - j];}}return dp[n];}
}
