数据结构刷题（三十）：96不同的二叉搜索树、01背包问题理论、416分割等和子集

一、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给占据了，只剩下j－wi的空间给前面i－1， 所以dp[i-1][j-weight[i]]的意思就是还没加上物品i的重量(weight[i])时的最大价值， 最后再加上i物品的价值

细节：1.当 j-weight【i】<0 时，数组会越界，要加个if j＜weight【i】则 dp【i】【j】=dp【i-1】【j】；

2.初始化时，当背包容量j=0时，不论i等于几，都默认为0；而i=0时，可以根据物品i=0的重量设定初始值。

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.需要注意本题中的重量也就是价值这一说法

（1）01背包的递推公式为：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;}
}