德州企业网站建设,wordpress下载站模板下载,营销型网站建设一般多少钱,温州自助建站公司● 343. 整数拆分
想不到#xff0c;要勇于看题解。
关键在于理解递推公式。
1、DP数组及其下标的含义#xff1a;dp[i]是分解i这个数得到的最大的乘积。
2、DP数组如何初始化#xff1a;dp[0]和dp[1]都没意义#xff0c;所以直接不赋值#xff0c;初始化dp[2]1即可。…● 343. 整数拆分
想不到要勇于看题解。
关键在于理解递推公式。
1、DP数组及其下标的含义dp[i]是分解i这个数得到的最大的乘积。
2、DP数组如何初始化dp[0]和dp[1]都没意义所以直接不赋值初始化dp[2]1即可。
3、递推公式根据题目给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 。可以分成两种情况①n拆分成2个正整数的和。②n拆分成大于2个正整数的和。
①的话dp[n]应该j*(n-j)的最大值②的话dp[n]应该等于j*dp[n-j]的最大值。j是从1遍历到i-1因为dp[n-j]是分解n-j这个数得到的最大的乘积所以至少分解了2次乘j就是至少分解了3次。
所以dp[n]应该取两种情况下的最大值,dp[n]max( j * ( n-j ), j * dp[n-j] )。这个dp[n]只是n包含j的时候分解的最大值和前面的n包含1……j-1的时候分解的最大值没有联系起来所以这个式子还是不对的。
因此dp[n]还要和自己比较和之前的j对应的最大值也就是最近一次更新的dp[n]比较最终才是最大值。
根据公式得到从2到10的最大乘积如下 校验发现正确。
4、遍历顺序
当然是从左到右从小到大小的数统计好了大的数就靠小的数的最大乘积来统计。i初始化了2所以应该是从3到n注意下标是对应的最后就是返回dp[n]。对于j一般认为从1到i-1比如4分解2个的话是1和3,2和2,3和1。j是1,2就统计到了所有的乘积因为后面的是对称的所以其实从1到i/2就行。发现分解成2个以上的话也是到i/2之前就能统计到最大值具体原因还不知道。
5、打印DP数组。 打印如上图发现没错。
代码
class Solution {
public:int integerBreak(int n) {vectorint dp(n1);dp[2]1; //初始化for(int i3;in;i){for(int j1;ji/2;j){dp[i]max({dp[i],j*(i-j),j*dp[i-j]}); //考虑k2和k2的情况更新dp[i]}}return dp[n];}
};
● 96.不同的二叉搜索树
n3的时候分为以1为头结点、以2为头结点和以3为头结点三种情况。所以对于所有n都是如此。
n3的时候数量是下面三个数量相加
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量。
那么令dp[i]就是i个节点组成的二叉搜索树的数量对于所有n数量是下面n个数量相加
元素1为头结点搜索树的数量dp[n-1] * dp[0]
……
元素n为头结点搜索树的数量 dp[0] * dp[n-1]。
1.dp[i]含义i个节点组成的二叉搜索树的数量
2.递推公式
3.初始化dp[0]1,dp[1]1注意dp[0]是1空树也是一棵搜索树。
4.遍历顺序同样的由小推大。
代码
class Solution {
public:int numTrees(int n) {vectorint dp(n1,0);dp[0]1;//初始化for(int i1;in;i){for(int j0;ji;j){ //求和公式dp[i]dp[j]*dp[i-1-j]; }}return dp[n];}
};
