怀宁做网站,工作顺利的祝福语,网站网站制作,发布平台是什么一、96. 不同的二叉搜索树 1.这个题比较难想递推公式#xff0c;
dp[3]#xff0c;就是元素1为头结点搜索树的数量 元素2为头结点BFS的数量 元素3为头结点BFS的数量
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结…一、96. 不同的二叉搜索树 1.这个题比较难想递推公式
dp[3]就是元素1为头结点搜索树的数量 元素2为头结点BFS的数量 元素3为头结点BFS的数量
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
用公式来说明就是
i 2, dp[i] dp[p - 1] dp[i - p]
2.需要注意dp数组的初始化
代码
class Solution {public int numTrees(int n) {// 初始化int[] dp new int[n 1];// 分别初始化节点为0和1时的情况dp[0] 1;dp[1] 1;// 讨论j作为根结点时的情况 从左侧dp[0]到右侧dp[0]for (int i 2; i n; i) {for (int j 1; j i; j){//对于第i个节点需要考虑1作为根节点直到i作为根节点的情况所以需要累加dp[i] dp[j - 1] * dp[i - j] ;}}return dp[n];}
}
二、01背包问题理论 dp[i][j]是在背包达到j重量时任取0-i中任意多个物品所达到的最大价值 其中i代表物品j代表背包容量 现在需要放入i物品到背包中需要对比不放物品i和放入物品i两种情况。
不放物品i直接就是dp[i-1][j]的最有情况放入物品i:确定放入i时则整个物品集就被分成两部分1到i-1和第i个同时物品i会把j空间里的wi给占据了只剩下jwi的空间给前面i1 所以dp[i-1][j-weight[i]]的意思就是还没加上物品i的重量(weight[i])时的最大价值 最后再加上i物品的价值
细节1.当 j-weight【i】0 时数组会越界要加个if jweight【i】则 dp【i】【j】dp【i-1】【j】
2.初始化时当背包容量j0时不论i等于几都默认为0而i0时可以根据物品i0的重量设定初始值。
3.当dp是二维数组时双层for循环是可以颠倒顺序的 三、01背包问题理论二
1.将二维数组转换成一维的滚动数组
2.dp[j]指的是容量为j时的最大价值
3.列表后面的值需要通过与前面的值(可能在第一次循环中就确定了dp[1]的值只能使用倒序才能获取到最开始的dp[1]而不是使用正序去更新dp[1])比较确定因此要先处理所以在嵌套for循环需要使用倒序 四、416. 分割等和子集
1.使用01背包思想以下四点是使用01背包解决这个题的要求
背包的体积为sum / 2。已知体积背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。满足01背包要求
2.需要注意本题中的重量也就是价值这一说法
101背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]); 本题相当于背包里放入数值那么物品i的重量是nums[i]其价值也是nums[i]。
2如果dp[j] j 说明集合中的子集总和正好可以凑成总和j
class Solution {public boolean canPartition(int[] nums) {if (nums.length 0 nums null)return false;int n nums.length;int sum 0;for (int num : nums) {sum num;}// 判断和是否为奇数if (sum % 2 1) return false;int target sum / 2;// dp[j]表示 当背包重量为j时所具有的最大价值(这个题价值也就是重量)int[] dp new int[target 1];for (int i 0; i n; i) {for (int j target; j nums[i]; j--){//物品 i 的重量是 nums[i]其价值也是 nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}}// 只需要对两个子集中的一个进行判断即可return dp[target] target;}
}
