代码随想录day33Java版

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-j dp[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数组 // 创建数组后，其中默认的值就是0 for (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]); } }