建设企业网站的具体步骤,山西省建设厅网站首页,做内贸的什么网站效果好,图文网站源码Day35343. 整数拆分力扣题目链接给定一个正整数 n#xff0c;将其拆分为至少两个正整数的和#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积。思路动规逻辑确定dp数组#xff08;dp table#xff09;以及下标的含义dp[i]指的是拆分数字i能得到的最大成绩d…Day35343. 整数拆分力扣题目链接给定一个正整数 n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。 返回你可以获得的最大乘积。思路动规逻辑确定dp数组dp table以及下标的含义dp[i]指的是拆分数字i能得到的最大成绩dp[i]确定递推公式比如要拆分10就要分析是2×8 3×7...这个可以通过一个循环解决每次从2开始循环拆分i并不断更新dp[i]的最大值dp数组如何初始化dp[2] 1是确定的但dp[0]和dp[1]设置初始值为0就行因为反正也不会从他们这里面选确定遍历顺序dp[i]是从前面得来的从前往后遍历举例推导dp数组5 - 2 * 3; 8 - 3 * (2 * 3); 10 - 2 *(3* (2*3) )时间复杂度O(n2)空间复杂度O(n)贪心逻辑只要n还大于4就把n分出来一个3然后把res再和最后的n相乘时间复杂度O(n)空间复杂度O(1)代码class Solution {public int integerBreak(int n) {if (n 1 || n 2) return 1;if (n 3) return 2;int res 1;while (n 4){n - 3;res * 3;}res * n;return res;}
}class Solution {public int integerBreak(int n) {int[] dp new int[n 1];dp[2] 1;//初始化for (int i 3; i n; i) {//外层计算dp[i]for (int j 2; j i; j) {//内层计算拆分的情况dp[i] Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));//从后面两个中挑选不断更新dp[i]最大值}}return dp[n];}
}96.不同的二叉搜索树力扣题目链接给定一个整数 n求以 1 ... n 为节点组成的二叉搜索树有多少种思路确定dp数组dp table以及下标的含义dp[i]是从1到i这些数字组成不同的二叉搜索树的个数确定递推公式dp[3] dp[0] * dp[2] dp[1] * dp[1] dp[2] * dp[0]1~3这三个元素组成的二叉搜索树个数1为头节点2为头节点3为头节点1为头节点左子树0个元素的二叉搜索树 * 右子树2个元素的二叉搜索树...dp数组如何初始化dp[0] 1, dp[1] 1确定遍历顺序从前往后举例推导dp数组代码class Solution {public int numTrees(int n) {int[] dp new int[n 1];dp[0] 1;dp[1] 1;//初始化dp数组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];}
}
