dw做网站怎么设置页面音乐,如何自创app软件,扬州企业做网站,网页设计与制作教程 pdf代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第九章 动态规划part03● 343.整数拆分
● 096.不同的二叉搜索树 详细布置 今天两题都挺有难度#xff0c;建议大家思考一下没思路#xff0c;直接看题解#xff0c;第一次做#xff0c;硬想很难想出来。343. 整数… 代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第九章 动态规划part03● 343.整数拆分
● 096.不同的二叉搜索树 详细布置 今天两题都挺有难度建议大家思考一下没思路直接看题解第一次做硬想很难想出来。343. 整数拆分 https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
视频讲解https://www.bilibili.com/video/BV1Mg411q7YJ96.不同的二叉搜索树 https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解https://www.bilibili.com/video/BV1eK411o7QA
目录
0343_整数拆分
0096_不同的二叉搜索树 0343_整数拆分
package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;public class _0343_整数拆分 {
}class Solution0343 {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 / 2; j) {dp[i] Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));}}return dp[n];}public int integerBreak2(int n) {if (n 2) return 1;if (n 3) return 2;if (n 4) return 4;int result 1;while (n 4) {result * 3;n - 3;}result * n;return result;}public int integerBreak3(int n) {//dp[i] 为正整数 i 拆分后的结果的最大乘积int[] dp new int[n 1];dp[2] 1;for (int i 3; i n; i) {for (int j 1; j i - j; j) {//这里的 j 其实最大值为 i-j,再大只不过是重复而已//并且在本题中我们分析 dp[0], dp[1]都是无意义的//j 最大到 i-j,就不会用到 dp[0]与dp[1]dp[i] Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));//j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j 再相乘//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。}}return dp[n];}
}
0096_不同的二叉搜索树
package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;public class _0096_不同的二叉搜索树 {
}class Solution0096 {public int numTrees(int n) {int dp[] new int[n 1];dp[0] 1;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];}public int numTrees2(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];}
}
