哈尔滨网站建设设计公司,wordpress防木马,开发公司制度,莱芜房产网新房整数拆分
题目#x1f517;
题目描述
给定一个正整数 n #xff0c;将其拆分为 k个正整数的和#xff08;k 2#xff09;#xff0c;并使这些整数的乘积最大化。
返回你可以获得的最大乘积 。
思路分析
dp数组含义#xff1a;dp[i]表示整数i拆分后的最大乘积。…整数拆分
题目
题目描述
给定一个正整数 n 将其拆分为 k个正整数的和k 2并使这些整数的乘积最大化。
返回你可以获得的最大乘积 。
思路分析
dp数组含义dp[i]表示整数i拆分后的最大乘积。递推公式dp[i] j * dp[i - j]dp数组初始化dp[0] 0, dp[1] 0, dp[2] 1
cpp代码
class Solution {
public:int integerBreak(int n) {vectorint dp(n1);dp[0] 0;dp[1] 0;dp[2] 1;for(int i 3; i n; i){for(int j 1; j i/2; j){dp[i] max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};不同的二叉搜索树
题目
题目描述
给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。
思路分析 dp数组含义dp[i]表示由i个节点组成的不同二叉搜索树的数量。递推公式从上图我们可以发现 dp[3] 以1为头节点的二叉树数量以2为头节点的二叉树数量以3为头节点的二叉树数量 其中 以1为头节点的二叉树数量 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量 以2为头节点的二叉树数量 右子树有1个元素的搜索树数量 * 左元素有1个元素的搜索树数量 以3为头节点的二叉树数量 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量 而 有2个元素的搜索树数量 dp[2] 有1个元素的搜索树数量 dp[1] 有0个元素的搜索树数量 dp[0] 因此可以推断出 d p [ i ] d p [ j − 1 ] ∗ d p [ i − j ] dp[i] dp[j - 1] * dp[i - j] dp[i]dp[j−1]∗dp[i−j]dp数组初始化dp[0] 1
cpp代码
class Solution {
public:int numTrees(int n) {vectorint dp(n1);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];}
};总结
这两题都是属于思路比较绕但想清楚之后会发现很简单的所以前期一定要理解dp数组的相关含义。
