网站代码在哪里修改,上海网站建设思创,青岛网站建设推广优化,免费个人网站在线制作343. 整数拆分
设dp[i]表示拆分 数字i 出来的正整数相乘值最大的值
(i - j) * j,和dp[i - j] * j是获得dp[i]的两种乘法#xff0c;在里面求最大值可以得到当前dp[i]的最大值#xff0c;但是这一次的得出的最大值如果赋值给dp[i]#xff0c;可能没有没赋值的dp[i]大#…343. 整数拆分
设dp[i]表示拆分 数字i 出来的正整数相乘值最大的值
(i - j) * j,和dp[i - j] * j是获得dp[i]的两种乘法在里面求最大值可以得到当前dp[i]的最大值但是这一次的得出的最大值如果赋值给dp[i]可能没有没赋值的dp[i]大具体例子的话没想只能说是覆盖了可能出现的问题。
所以是dp[i] max({dp[i], (i - j) * j, dp[i - j] * j});
初始化dp[0]0,dp[1]1或者dp[2]1都可以我觉得初始化dp[2]1比较合适一些同意卡哥的看法。
先便利要求的 i然后再遍历 求最大值的 j
class Solution {public:int integerBreak(int n) {vectorint dp(n 1);dp[2] 1;for (int i 3; i n ; i) {for (int j 1; j i; j) {dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}};
96.不同的二叉搜索树
二叉搜索树是一个有序树。
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树 设dp[i]的含义是以1....到 i 构成的二叉搜索树为dp[i]种。
dp[i]该怎么从其他状态推出来呢 联系起n1和n2与n3之间构成的不同的二叉搜索数的数量关系。很抽象我也不知道怎么联系起来的
抽象后发现dp[i]以1.....到i的各个节点为头节点的不同二叉搜索树之和
比如dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]分别以123为头节点的不同二叉搜索树的数量加起来等于 以1....到 i 构成的二叉搜索树 总数 .
最后再抽象一层变成j从1开始
dp[i] dp[j - 1] * dp[i - j]; 初始化依照二叉搜索树的定义没有一个节点也可以算是二叉搜索树所以 dp[0] 1; 最后代码
class Solution {
public:int numTrees(int n) {vectorint dp(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];}
}; i 算从1开始推到i的dp[i] j 算从每一阶段的dp[i]内的1....i位置的不同头节点二叉搜索树之和然后求出那个阶段的dp[i]
