动态规划、背包问题 6/25 110-115

1.整数拆分（ LeetCode 343 ）

方法一：动态规划
动态规划考虑状态要全面

class Solution {
    
        public int integerBreak(int n) {
    
            int dp[] = new int[n + 1];//dp[i] = 拆分i获得的最大乘积
            dp[1] = 0;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
    
                int max = Integer.MIN_VALUE;
                for (int j = 1; j < i; j++) {
    
                    /* 初次做题为考虑完所有状态 dp[i] = 拆分数字i所获得的最大成绩 dp[i]的状态转移有两种情况： 情况一：拆分数 > 2 dp[i] = dp[i - j] * j 的最大值 情况二：拆分数 = 2 dp[i] = j * (i - j) 的最大值 每次选取 dp[i - j] * j 与 j * (i - j) 中的最大值 */
                    max = Math.max(max,Math.max(j * dp[i - j],j * (i - j)));
                }
                dp[i] = max;
            }
            return dp[n];
        }
    }

方法二：对方法一进行优化
利用了一定的数学知识

  //整数拆分
    class Solution {
    
        public int integerBreak(int n) {
    
            //dp[i] 置为i时的最优解
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
    
                //根据数学分析，只需考虑如下四种值的情况
                int x = Math.max(2 * (i - 2),2 * dp[i - 2]);
                int y = Math.max(3 * (i - 3),3 * dp[i - 3]);
                dp[i] = Math.max(x,y);
            }
            return dp[n];
        }
    }

方法三:数学解决方案
不要求掌握,但要记住此类型的解决方案

//整数拆分
    //数学相关，了解即可 不要求掌握此解
    class Solution {
    
        public int integerBreak(int n) {
    
            //当 n < 4时单独考虑
            if (n == 2)return 1;
          if (n == 3)return 2;
          //当 n >= 时
            int x = n / 3;
            int y = n % 3;
            //如果余数为0，则全部拆分为3
            if (y == 0)return (int) Math.pow(3,x);
            //余数为1则拆出两个2，其余为3
            else if (y == 1)return (int) (Math.pow(3,x - 1) * 4);
            //余数为1则拆出一个2，其余为3
            else if (y == 2)return (int) (Math.pow(3,x) * 2);
            return -1;
        }
    }

2.不同的二叉搜索树（ LeetCode 96 ）

动态规划

 class Solution {
    
        /* dp[i] = i个不同的数组成的二叉搜索数的个数 假设 i = 5 当根节点等于 1 时 ，其余数字都比1大，只能在右边 dp[i] += dp[4] 当根节点等于 2 时，左边有一个1比2小，右边有三个比2大的数字 dp[i] += dp[1] * dp[3] 当根节点等于 3 时，左边有两个数比3小，右边有两个数比3大的数字 dp[i] += dp[2] * dp[2] ... 知道根节点等于5，左边有4个数字比5小，只能放在5的左边,dp[i] += dp[4] */
        public int numTrees(int n) {
    
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
    
                for (int j = 1; j <= i; j++) {
    
                    int leftNum = dp[j - 1];
                    int rightNum = dp[i - j];
                    dp[i] += leftNum * rightNum;
                }
            }
            return dp[n];
        }
    }

3.打家劫舍（ LeetCode 198 ）

动态规划

class Solution {
    
        public int rob(int[] nums) {
    
            int n = nums.length;
            int[] T =  new int[n];//第i家偷了的最大利润
            int[] B = new int[n];//第i家没有偷的最大利润
            T[0] = nums[0];
            B[0] = 0;
            for (int i = 1; i < n; i++) {
    
                //如果这一家不偷的话，等于前一家偷的最大利润或前一天不偷的利润的最大值
                B[i] = Math.max(T[i - 1],B[i - 1]);
                T[i] = B[i - 1] + nums[i];//如果这一家偷了，前一家不能偷
            }
            return Math.max(T[n - 1],B[n - 1]);
        }
    }

方法二：动态规划优化
优化空间复杂度

class Solution {
    
        public int rob(int[] nums) {
    
            int n = nums.length;
            int T =  nums[0];//第i家偷了的最大利润
            int B = 0;//第i家没有偷的最大利润
            for (int i = 1; i < n; i++) {
    
                int preB = B;
                //如果这一家不偷的话，等于前一家偷的最大利润或前一天不偷的利润的最大值
                B = Math.max(T,B);
                T = preB + nums[i];//如果这一家偷了，前一家不能偷
            }
            return Math.max(T,B);
        }
    }

4.打家劫舍II（ LeetCode 213 ）

动态规划
比上一题多了两个状态

class Solution {
    
        public int rob(int[] nums) {
    
            //第一天偷
            int n = nums.length;
            int T =  nums[0];//第i家偷了的最大利润 (第一家偷了时)
            int B = 0;//第i家没有偷的最大利润 (第一家偷了时)
            int T2 = 0; // (第一家没偷了时)
            int B2 = 0; // (第一家没偷了时)
            for (int i = 1; i < n; i++) {
    
                if (i < n - 1){
    //最后一家不可以偷
                    int preB = B;
                    //如果这一家不偷的话，等于前一家偷的最大利润或前一天不偷的利润的最大值
                    B = Math.max(T,B);
                    T = preB + nums[i];//如果这一家偷了，前一家不能偷
                }
                //最后一家可以偷
                int preB2 = B2;
                B2 = Math.max(T2,B2);
                T2 = preB2 + nums[i];
            }
          
            return Math.max(Math.max(T,B),Math.max(T2,B2));
        }
    }

5.打家劫舍III（ LeetCode 337 ）

动态规划 + 利用递归特性

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution {
    
        public int rob(TreeNode root) {
    
            int[] arr = dfs(root);
            return  Math.max(arr[0],arr[1]);
        }

        /** * 返回在node处偷与不偷各自的最大利润 * @param node * @return arr = new int[2],arr[0] 不偷时的最大利润，arr[1] 偷时的最大利润 */
        public int[] dfs(TreeNode node){
    
            if (node == null)return new int[]{
    0,0};
            if (node.left == null && node.right == null)return new int[]{
    0,node.val};
            int[] larr = dfs(node.left);
            int[] rarr = dfs(node.right);
            int[] ans = new int[2];
            //本节点不偷钱时的最大利润 = 左右孩子分别的最大利润之和
            ans[0] = Math.max(larr[0],larr[1]) + Math.max(rarr[0],rarr[1]);
            //本节点偷钱时的最大利润 = 本节点的金额 + 左、右孩子不偷钱的最大利润
            ans[1] = node.val + larr[0] + rarr[0];
            return ans;
        }
    }