培训机构活动策划网站,广西电力工程建设有限公司网站,做机械设计的要知道哪些网站,网上怎么接单做网站Leetcode 343. 整数拆分
题目链接 343 整数拆分
dp[i]的含义对i进行拆分#xff0c;得到最大的整数
固定一个j用for循环来遍历#xff0c;剩下的按照i-j来算#xff0c;拆分成两个数是j*(i-j)#xff0c;拆分为三个及其以上需要j*dp[i-j],下面上代码#xff1a;
class…Leetcode 343. 整数拆分
题目链接 343 整数拆分
dp[i]的含义对i进行拆分得到最大的整数
固定一个j用for循环来遍历剩下的按照i-j来算拆分成两个数是j*(i-j)拆分为三个及其以上需要j*dp[i-j],下面上代码
class Solution {
public:int integerBreak(int n) {vectorint dp(n 1);//vector数组定义dp[2] 1;for(int i3;in;i){for(int j1;ji;j){dp[i] max(dp[i],max(dp[i-j]*j,(i-j)*j));}} return dp[n];}
};
Leetcode 96. 不同的二叉搜索树
题目链接 96 不同的二叉搜索树
本题目有点找规律的意思。
dp[i]是由dp[0],dp[1].dp[2]来推出来的 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]
在上面的分析中其实已经看出其递推关系 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素从1遍历到i为止。
所以递推公式dp[i] dp[j - 1] * dp[i - j]dp[1],dp[2]在递推公式中可以推断出所以不用初始化; j-1 为j为头结点左子树节点数量左边的节点一定小于ji-j 为以j为头结点右子树节点数量右边的节点一定大于j
零个节点也是二叉搜索树。
下面上代码
class Solution {
public:int numTrees(int n) {vectorintdp(n1);dp[0] 1;for(int i1;in;i){for(int j1;ji;j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
};
end
