网站做seo,网站查询地址,什么网站的注册是动态,网站集群建设和网站集约化96.不同的二叉搜索树
递推公式不好想#xff0c;在根节点的左右组装#xff0c;从dp[0]*dp[n-1]到dp[n-1]*dp[0]累加
class Solution {public int numTrees(int n) {//初始化 dp 数组int[] dp new int[n 1];//初始化0个节点和1个节点的情况dp[0] 1;dp[1] 1;for (int i …96.不同的二叉搜索树
递推公式不好想在根节点的左右组装从dp[0]*dp[n-1]到dp[n-1]*dp[0]累加
class Solution {public int numTrees(int n) {//初始化 dp 数组int[] dp new int[n 1];//初始化0个节点和1个节点的情况dp[0] 1;dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {//对于第i个节点需要考虑1作为根节点直到i作为根节点的情况所以需要累加//一共i个节点对于根节点j时,左子树的节点个数为j-1右子树的节点个数为i-jdp[i] dp[j - 1] * dp[i - j];}}return dp[n];}
}
01背包
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp数组int goods weight.length; // 获取物品的数量int[][] dp new int[goods][bagSize 1];// 初始化dp数组// 创建数组后其中默认的值就是0for (int j weight[0]; j bagSize; j) {dp[0][j] value[0];}// 填充dp数组for (int i 1; i weight.length; i) {for (int j 1; j bagSize; j) {if (j weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] dp[i-1][j];} else {/*** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]);}}}
01背包II
用到了滚动数组进行状态压缩
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen weight.length;//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//遍历顺序先遍历物品再遍历背包容量for (int i 0; i wLen; i){for (int j bagWeight; j weight[i]; j--){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}
