背包

416.分割等和子集

动态规划 - 状态转移方程

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         if(nums.length < 2) {
  4.             return false;
  5.         }
  6.         int sum = 0, max = 0;
  7.         for(int n : nums) {
  8.             sum += n;
  9.             max = Math.max(n, max);
  10.         }
  11.         if((sum & 1) == 1) {
  12.             return false;
  13.         }
  14.         int target = sum / 2;
  15.         if(max > target) {
  16.             return false;
  17.         }
  18.         // 状态转移表
  19.         boolean[][] status = new boolean[nums.length][target + 1];
  20.         for(int i = 0; i < nums.length; i++) {
  21.             status[i][0] = true;
  22.         }
  23.         status[0][nums[0]] = true;
  24.         // status 放置的是每个阶段 [0, target] 区间有无到达过
  25.         for(int i = 1; i < nums.length; i++) {
  26.             int num = nums[i];
  27.             for(int j = 1; j <= target; j++) {
  28.                 if(j >= num) {
  29.                     // 核心点在这
  30.                     status[i][j] = status[i - 1][j] || status[i - 1][j - num];
  31.                 } else {
  32.                     status[i][j] = status[i - 1][j];
  33.                 }
  34.             }
  35.         }
  36.         return status[nums.length - 1][target];
  37.     }
  38. }

动态规划-状态转移方程-一维数组

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int n = nums.length;
  4.         if(n < 2) {
  5.             return false;
  6.         }
  7.         int sum = 0, max = 0;
  8.         for(int num : nums) {
  9.             sum += num;
  10.             max = Math.max(num, max);
  11.         }
  12.         if((sum & 1) == 1) {
  13.             return false;
  14.         }
  15.         int target = sum / 2;
  16.         if(max > target) {
  17.             return false;
  18.         }
  20.         boolean[] dp = new boolean[target + 1];
  21.         dp[0] = true;
  22.         for(int i = 1; i < n; i++) {
  23.             int num = nums[i];
  24.             for(int j = target; j >= num; j--) {
  25.                 dp[j] |= dp[j - num]; 
  26.             }
  27.         }
  28.         return dp[target];
  29.     }
  30. }

494.目标和

回溯

  1. class Solution {
  3.     private int count = 0;
  5.     public int findTargetSumWays(int[] nums, int target) {
  6.         backtrace(nums, 0, target, 0);
  7.         return count;
  8.     }
  10.     private void backtrace(int[] nums, int stage, int target, int sum) {
  11.         if(stage == nums.length) {
  12.             if(sum == target) {
  13.                 count++;
  14.             }
  15.             return;
  16.         }
  17.         backtrace(nums, stage + 1, target, sum + nums[stage]);
  18.         backtrace(nums, stage + 1, target, sum - nums[stage]);
  19.     }
  20. }

动态规划-状态转移方程-solution0

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         int n = nums.length;
  4.         int sum = 0;
  5.         for(int i = 0; i < n; i++) {
  6.             sum += nums[i];
  7.         }
  9.         if(sum < Math.abs(target)) {
  10.             return 0;
  11.         }
  13.         // 状态数组，dp[i][j]，表示从数组nums中 0 - i 的元素进行加减可以得到 j 的方法数量。
  14.         // 这里不能压缩成一维数组，因为当前阶段的状态dp[i][j]，需要根据 dp[i][j - nums[i]] 和 dp[i][j + nums[i]] 来决定的
  15.         // 压缩到一维数组后，如果从前往后遍历 dp[i][j - nums[i]] 则有可能不是当前阶段状态， 如果从后往前遍历，dp[i][j + nums[i]] 则有可能不是当阶段的状态
  16.         int m = sum * 2 + 1;
  17.         int[][] dp = new int[n][m];
  19.         // 状态转移方程
  20.         // dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
  22.         // 初始化
  23.         // 当 nums[0] == 0 时，dp[0][sum - 0] = 1，   dp[0][sum + 0] = 1，即dp[0][sum] = 2，这里的sum表示nums中执行全部执行加/减能达到的数，画出二维表格，sum 也是中间点，即代表 0 的位置
  24.         if(nums[0] == 0) {
  25.             dp[0][sum] = 2;
  26.         } else {
  27.             dp[0][sum - nums[0]] = 1;
  28.             dp[0][sum + nums[0]] = 1;
  29.         }
  31.         for(int i = 1; i < n; i++) {
  32.             for(int j = 0; j < m; j++) {
  33.                 if(j - nums[i] >= 0) {
  34.                     dp[i][j] = dp[i - 1][j - nums[i]];
  35.                 }
  36.                 if(j + nums[i] < m) {
  37.                     dp[i][j] += dp[i - 1][j + nums[i]];
  38.                 }
  39.             }
  40.         }
  41.         return dp[n - 1][sum + target];
  42.     }
  43. }

动态规划-状态转移方程-solution1

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         // 记数组之和为 sum，添加符号为 - 的元素之和为 neg，则其余添加符号为 + 的元素之和为 sum - beg
  4.         // 那么可推导出 (sum - neg) - neg = sum - 2 * neg = target => neg = (sum - target) / 2
  5.         // 由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数，所以上式成立的前提是 sum - target 是非负偶数。若不符合该条件可直接返回 0。
  6.         int n = nums.length;
  7.         int sum = 0;
  8.         for(int i = 0; i < nums.length; i++) {
  9.             sum += nums[i];
  10.         }
  11.         int diff = sum - target;
  12.         if(diff < 0 || diff % 2 != 0) {
  13.             return 0;
  14.         }
  16.         int neg = diff / 2;
  18.         // 此时转换成 0 - 1 背包问题，dp[i][j] 表示从数组nums中 0 - i 中选择元素进行相加可以得到 j 的方法数量
  19.         // 状态转移方程
  20.         // j < nums[i] dp[i][j] = dp[i - 1][j]
  21.         // j >= nums[i]  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
  22.         int[][] dp = new int[n][neg + 1];
  23.         dp[0][0] = 1;
  24.         if(nums[0] == 0) {
  25.             dp[0][0] = 2;
  26.         } else if(nums[0] <= neg) {
  27.             dp[0][nums[0]] = 1;
  28.         }
  29.         for(int i = 1; i < n; i++) {
  30.             int num = nums[i];
  31.             for(int j = 0; j <= neg; j++) {
  32.                 dp[i][j] = dp[i - 1][j];
  33.                 if(j >= num) {
  34.                     dp[i][j] += dp[i - 1][j - num];
  35.                 }
  36.             }
  37.         }
  38.         return dp[n - 1][neg];
  39.     }
  40. }

动态规划-状态转移方程-一维数组

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         // 记数组之和为 sum，添加符号为 - 的元素之和为 neg，则其余添加符号为 + 的元素之和为 sum - beg
  4.         // 那么可推导出 (sum - neg) - neg = sum - 2 * neg = target => neg = (sum - target) / 2
  5.         // 由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数，所以上式成立的前提是 sum - target 是非负偶数。若不符合该条件可直接返回 0。
  6.         int n = nums.length;
  7.         int sum = 0;
  8.         for(int i = 0; i < nums.length; i++) {
  9.             sum += nums[i];
  10.         }
  11.         int diff = sum - target;
  12.         if(diff < 0 || diff % 2 != 0) {
  13.             return 0;
  14.         }
  16.         int neg = diff / 2;
  18.         // 此时转换成 0 - 1 背包问题，dp[i][j] 表示从数组nums中 0 - i 中选择元素进行相加可以得到 j 的方法数量
  19.         // 状态转移方程
  20.         // j < nums[i] dp[i][j] = dp[i - 1][j]
  21.         // j >= nums[i]  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
  22.         // 压缩空间，从二维数组压缩至一维数组
  23.         int[] dp = new int[neg + 1];
  24.         dp[0] = 1;
  25.         if(nums[0] == 0) {
  26.             dp[0] = 2;
  27.         } else if(nums[0] <= neg) {
  28.             dp[nums[0]] = 1;
  29.         }
  30.         for(int i = 1; i < n; i++) {
  31.             int num = nums[i];
  32.             for(int j = neg; j >= 0; j--) {
  33.                 if(j >= num) {
  34.                     dp[j] += dp[j - num];
  35.                 }
  36.             }
  37.         }
  38.         return dp[neg];
  39.     }
  40. }

322.零钱兑换

回溯

解题思路：
单纯用回溯，会存在大量的重放子问题，需要去掉，使用数组 count 来记录当硬币面额达到 1 ~ amount 之间时，需要的最少硬币数

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         if(amount == 0) {
  4.             return 0;
  5.         }
  6.         return backtrace(coins, amount, new int[amount + 1]);
  7.     }
  9.     // backtrace 函数返回的是每个可能出现的 amount 阶段，需要的最少硬币数
  10.     private int backtrace(int[] coins, int amount, int[] count) {
  11.         if(amount < 0) {
  12.             return -1;
  13.         }
  14.         if(amount == 0) {
  15.             return 0;
  16.         }
  17.         if(count[amount] != 0) {
  18.             return count[amount];
  19.         }
  20.         int min = Integer.MAX_VALUE;
  21.         for(int i = 0; i < coins.length; i++) {
  22.            int res = backtrace(coins, amount - coins[i], count);
  23.             if(res != -1 && res < min) {
  24.                 min = res + 1;
  25.             }
  26.         }
  27.         count[amount] = min == Integer.MAX_VALUE ? -1 : min;
  28.         return count[amount];
  29.     }
  30. }

完全背包-求最小值问题

解题思路：将题目转化为完全背包-求最小值问题

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         // 定义状态：
  4.         // dp[i][j] 表示第 i 个面额的硬币决策完后，金额能达到 j 的最少硬币个数
  5.         // 状态转移方程为：dp[i][j] = min(dp[i][j - (0 ~ k) * coins])
  6.         int n = coins.length;
  7.         int[][] dp = new int[n][amount + 1];
  8.         for(int i = 0; i < n; i++){
  9.             Arrays.fill(dp[i], Integer.MAX_VALUE);
  10.         }
  11.         // 初始化第一层
  12.         for(int i = 0; i  <=  amount / coins[0]; i++) {
  13.             dp[0][i * coins[0]] = i;
  14.         }
  16.         for(int i = 1; i < n; i++) {
  17.             for(int j = 0; j <= amount; j++) {
  18.                 int k = j / coins[i];
  19.                 for(int c = 0; c <= k; c++) {
  20.                     if(j >= c * coins[i] && dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE) {
  21.                         dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - c * coins[i]] + c);
  22.                     }
  23.                 } 
  24.             }
  25.         }
  26.         return dp[n - 1][amount] == Integer.MAX_VALUE ? -1 : dp[n - 1][amount];
  27.     }
  28. }

518.零钱兑换II

动态规划 - 状态转移方程

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         // 0-1背包问题，计数
  4.         // 边界条件
  5.         if(amount == 0) {
  6.             return 1;
  7.         }
  8.         // 定义状态
  9.         // dp[i] 表示总金额为 i 时，硬币的组合个数
  10.         // 状态转移方程式： i > coins[j], dp[i] = sum(dp[i - coins[j]])
  11.         int[] dp = new int[amount + 1];
  12.         dp[0] = 1;
  13.         for(int coin : coins) {
  14.             for(int i = coin; i <= amount; i++) {
  15.                 dp[i] += dp[i - coin];
  16.             }
  17.         }
  18.         return dp[amount];        
  19.     }
  20. }

完全背包-求计数问题

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         // 定义状态：dp[i][j] 表示第 i 个面额的硬币决策完后，能到达金额 j 的的硬币组合个数
  4.         // 状态转移方程：dp[i][j] = sum(dp[i - 1][j - (0 ~ k) * coins[i]])
  5.         int n = coins.length;
  6.         int[][] dp = new int[n][amount + 1];
  8.         // 初始化第一层
  9.         for(int k = 0; k <= amount / coins[0]; k++) {
  10.             dp[0][k * coins[0]] = 1;
  11.         }
  13.         for(int i = 1; i < n; i++) {
  14.             int coin = coins[i];
  15.             for(int j = 0; j <= amount; j++) {
  16.                 int k = j /  coin;
  17.                 for(int c = 0; c <= k; c++) {
  18.                     dp[i][j] += dp[i - 1][j - c * coin];
  19.                 }
  20.             }
  21.         }
  23.         return dp[n - 1][amount];
  24.     }
  25. }

路径问题

62.不同路径

动态规划

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         // 多阶段决策模型 - (m + n - 2) 个阶段
  4.         // 状态定义: dp[m][n] 为可到达当前网格的总路径数
  5.         int[][] dp = new int[m][n];
  6.         // 状态转移方程式：dp[m][n] = dp[m][n - 1] + dp[m - 1][n]  
  7.         // 初始化
  8.         for(int i = 0; i < m; i++) {
  9.             dp[i][0] = 1;
  10.         }
  11.         for(int i = 0; i < n; i++) {
  12.             dp[0][i] = 1;
  13.         }
  15.         for(int i = 1; i < m; i++) {
  16.             for(int j = 1; j < n; j++) {
  17.                 dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
  18.             }
  19.         }
  20.         return dp[m - 1][n - 1];
  21.     }
  22. }

63.不同路径II

动态规划

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int m = obstacleGrid.length, n = obstacleGrid[0].length;
  4.         int[][] dp = new int[m][n];
  6.         // 状态转移方程
  7.         // obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j] != 1 && dp[i - 1][j] != 0, dp[i][j] += dp[i - 1][j] 
  8.         // obstacleGrid[i][j - 1] != 1 && obstacleGrid[i][j] != 1 && dp[i][j - 1] != 0,, dp[i][j] += dp[i][j - 1]
  9.         for(int i = 0; i < m; i++) {
  10.             if(obstacleGrid[i][0] == 1) {
  11.                 break;
  12.             }
  13.             dp[i][0] = 1;
  14.         }
  15.         for(int i = 0; i < n; i++) {
  16.             if(obstacleGrid[0][i] == 1) {
  17.                 break;
  18.             }
  19.             dp[0][i] = 1;
  20.         }
  22.         for(int i = 1; i < m; i++) {
  23.             for(int j = 1; j < n; j++) {
  24.                 if(obstacleGrid[i][j] == 0) {
  25.                     if(obstacleGrid[i][j - 1] != 1 && dp[i][j - 1] != 0) {
  26.                         dp[i][j] += dp[i][j - 1];
  27.                     }
  29.                     if(obstacleGrid[i - 1][j] != 1 && dp[i - 1][j] != 0) {
  30.                         dp[i][j] += dp[i - 1][j];
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.         return dp[m - 1][n - 1];
  36.     }
  37. }

64.最小路径和

动态规划

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         // 状态定义：dp[m][n] 为左上角到 dp[m][n] 这个格子的最小路径和
  4.         // 状态转移方程：dp[m][n] = Math.min(dp[m - 1][n], dp[m][n - 1]) + grid[m][n]
  5.         int m = grid.length, n = grid[0].length;
  6.         int[][] dp = new int[m][n];
  7.         dp[0][0] = grid[0][0];
  8.         for(int i = 1; i < m; i++) {
  9.             dp[i][0] = dp[i - 1][0] + grid[i][0];  
  10.         }
  12.         for(int i = 1; i < n; i++) {
  13.             dp[0][i] = dp[0][i - 1] + grid[0][i];
  14.         }
  16.         for(int i = 1; i < m; i++) {
  17.             for(int j = 1; j < n; j++) {
  18.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  19.             }
  20.         }
  22.         return dp[m - 1][n - 1];
  23.     }
  24. }

剑指Offer 47.礼物的最大价值

动态规划

  1. class Solution {
  2.     public int maxValue(int[][] grid) {
  3.         // 状态定义：dp[m][n] 为左上角到 dp[m][n] 这个格子的最小路径和
  4.         // 状态转移方程：dp[m][n] = Math.max(dp[m - 1][n], dp[m][n - 1]) + grid[m][n]
  5.         int m = grid.length, n = grid[0].length;
  6.         int[][] dp = new int[m][n];
  7.         dp[0][0] = grid[0][0];
  8.         for(int i = 1; i < m; i++) {
  9.             dp[i][0] = dp[i - 1][0] + grid[i][0];  
  10.         }
  12.         for(int i = 1; i < n; i++) {
  13.             dp[0][i] = dp[0][i - 1] + grid[0][i];
  14.         }
  16.         for(int i = 1; i < m; i++) {
  17.             for(int j = 1; j < n; j++) {
  18.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  19.             }
  20.         }
  22.         return dp[m - 1][n - 1];
  23.     }
  24. }

120.三角形最小路径和

动态规划-二维数组

  1. class Solution {
  2.     public int minimumTotal(List<List<Integer>> triangle) {
  3.         int size = triangle.size();
  4.         // 定义状态 dp[i][j] 即为到达 第i行，第j个元素的最小路径
  5.         // 状态转移方程：
  6.         // i - 1 >= 0 && j - 1 >= 0  dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j)
  7.         // i - 1 > 0 && j == triangle.get(i).size()  dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j)
  8.         int[][] dp = new int[size][size];
  9.         dp[0][0] = triangle.get(0).get(0);
  10.         for(int i = 1; i < size; i++) {
  11.             dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
  12.         }
  13.         for(int i = 1; i < size; i++) {
  14.             for(int j = 1; j < triangle.get(i).size(); j++) {
  15.                 if(j == triangle.get(i - 1).size()) {
  16.                     dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
  17.                 } else {
  18.                     dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
  19.                 }
  20.             }
  21.         }
  22.         int min = Integer.MAX_VALUE;
  23.         for(int i = 0; i < size; i++) {
  24.             min = Math.min(dp[size - 1][i], min);
  25.         }
  26.         return min;
  27.     }
  28. }

动态规划-一维数组

  1. class Solution {
  2.     public int minimumTotal(List<List<Integer>> triangle) {
  3.         int size = triangle.size();
  4.         // 定义状态 dp[i][j] 即为到达 第i行，第j个元素的最小路径
  5.         // 状态转移方程：
  6.         // i - 1 >= 0 && j - 1 >= 0  dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j)
  7.         // i - 1 > 0 && j == triangle.get(i).size()  dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j)
  8.         int[] dp = new int[size];
  9.         dp[0] = triangle.get(0).get(0);
  10.         for(int i = 1; i < size; i++) {
  11.             for(int j = triangle.get(i).size() - 1; j >= 0; j--) {
  12.                 if(j == triangle.get(i - 1).size()){
  13.                     dp[j] = dp[j - 1] + triangle.get(i).get(j);
  14.                 } else if(j == 0) {
  15.                     dp[j] = dp[j] + triangle.get(i).get(j);
  16.                 } else {
  17.                     dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j);
  18.                 }
  19.             }
  20.         }
  21.         int min = Integer.MAX_VALUE;
  22.         for(int i = 0; i < size; i++) {
  23.             min = Math.min(dp[i], min);
  24.         }
  25.         return min;
  26.     }
  27. }

打家劫舍 & 买卖股票

198.打家劫舍

动态规划

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int n = nums.length;
  4.         int[] dp = new int[n];
  5.         for(int i = 0; i < n; i++) {
  6.             if(i - 2 >= 0) {
  7.                 for(int j = i - 2; j >= 0; j--) {
  8.                     dp[i] = Math.max(dp[i], dp[j]);
  9.                 }
  10.                 dp[i] += nums[i];
  11.             } else {
  12.                 dp[i] += nums[i];
  13.             }
  14.         }
  15.         int max = Integer.MIN_VALUE;
  16.         for(int i = 0; i < n; i++) {
  17.             max = Math.max(max, dp[i]);
  18.         }
  19.         return max;
  20.     }
  21. }

动态规划-状态转移方程

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int n = nums.length;
  4.         // 定义状态：dp[i] 表示当前第一间房到第 i + 1间房之间，能偷窃的最高金额
  5.         // 定义状态转移方程
  6.         // 对于第 i 间房有两种选项，偷与不偷
  7.         // 偷的情况 dp[i] = dp[i - 2] + nums[i];
  8.         // 不偷的情况 dp[i] = dp[i - 1];
  9.         // 那么能偷窃的最高金额 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) 
  10.         int[] dp = new int[n];
  11.         dp[0] = nums[0];
  12.         if(n == 1) {
  13.             return dp[0];
  14.         }
  15.         dp[1] = Math.max(nums[0], nums[1]);
  16.         if(n == 2) {
  17.             return dp[1];
  18.         }
  19.         for(int i = 2; i < n; i++) {
  20.             dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]) ;
  21.         }
  22.         return dp[n - 1];
  23.     }
  24. }

213.打家劫舍II

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int n = nums.length;
  4.         // 定义状态：dp[i] 表示当前第一间房到第 i + 1间房之间，能偷窃的最高金额
  5.         // 定义状态转移方程：dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  6.         // 由于房屋是围成一圈的，第一个房屋和最后一个房屋是紧挨着的，所以当k为最后一间屋时，
  7.         // 偷的情况 1 ~ k 房之间求 dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  8.         // 不偷的情况 0 ~ k - 1 房之间求 dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  9.         // 比较这两种情况的最大值
  10.         if(n == 1) {
  11.             return nums[0];
  12.         }
  13.         if(n == 2) {
  14.             return Math.max(nums[0], nums[1]);
  15.         } 
  16.         return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
  17.     }
  19.     private int robRange(int[] nums, int start, int end) {
  20.         int preTwo = nums[start], pre = Math.max(nums[start], nums[start + 1]);
  21.         for(int i = start + 2; i <= end; i++) {
  22.             int temp = pre;
  23.             pre = Math.max(preTwo + nums[i], pre);
  24.             preTwo = temp;
  25.         }
  26.         return pre;
  27.     }
  28. }

337.打家劫舍III (树形DP)

  1. class Solution {
  2.     public int rob(TreeNode root) {
  3.         // 定义状态：
  4.         // 每个节点有偷与不偷状态
  5.         // money[0] 表示当前节点-不偷累计的最高金额
  6.         // money[1] 表示当前节点-偷累计的最高金额
  7.         // Math.max(money[0], money[1]) 表示当前节点累计的最高累计金额
  8.         // 状态转移方程
  9.         // 当前节点 node 选择不偷时，money[0] = Math.max(left.menoy[0], left.menoy[1]) + Math.max(right.menoy[0], right.menoy[1])
  10.         // 当前节点 node 选择偷时， money[1] = left.menoy[0] + right.menoy[0] + node.val
  11.         int[] money = postorder(root);
  12.         return Math.max(money[0], money[1]);
  13.     }
  15.     private int[] postorder(TreeNode root) {
  16.         if(root == null) {
  17.             return new int[]{0, 0};
  18.         }
  19.         int[] left = postorder(root.left);
  20.         int[] right = postorder(root.right);
  21.         int[] money = new int[2];
  22.         // 不偷
  23.         money[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
  24.         // 偷
  25.         money[1] = left[0] + right[0] + root.val;
  26.         return money;
  27.     }
  28. }

714.买卖股票的最佳时机含手续

  1. class Solution {
  2.     public int maxProfit(int[] prices, int fee) {
  3.         // 定义状态：i 从 0 开始
  4.         // dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润
  5.         // dp[i][1] 表示第 i 天交易完后手里持有一只股票的最大利润
  6.         // 状态转移方程：
  7.         // dp[i][0] = max{dp[i - 1][0], dp[i - 1][1] + prices[i] - fee}
  8.         // dp[i][1] = max{dp[i - 1][0] - prices[i], dp[i - 1][1]}
  9.         int n = prices.length;
  10.         int[][]dp = new int[n][2];
  11.         dp[0][0] = 0;
  12.         dp[0][1] = -prices[0];
  14.         for(int i = 1; i < n; i++) {
  15.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
  16.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  17.         }
  19.         return Math.max(dp[n - 1][0], dp[n - 1][1]);
  20.     }
  21. }

309.最佳买卖股票时机含冷冻期

动态规划-1

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         // 定义状态： i 从 0 开始
  4.         // dp[i][0] 表示第 i 天不持有股票的最大利润
  5.         // dp[i][1] 表示第 i 天持有股票的最大利润
  6.         // 状态转移方程：
  7.         // 当 i == 0 时，结果为0
  8.         // 当 i < 1 时：
  9.         // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
  10.         // dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
  11.         // 当 i > 1 时：
  12.         // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
  13.         // dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
  14.         int n = prices.length;
  15.         if(n == 1) {
  16.             return 0;
  17.         }
  18.         int[][] dp = new int[n][2];
  19.         dp[0][0] = 0;
  20.         dp[0][1] = -prices[0];
  21.         dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
  22.         dp[1][1] = Math.max(dp[0][0] - prices[1], dp[0][1]);
  23.         for(int i = 2; i < n; i++) {
  24.             dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
  25.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
  26.         }
  27.         return Math.max(dp[n - 1][0], dp[n - 1][1]);
  28.     }
  29. }

动态规划-2

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         // 定义状态： i 从 0 开始
  4.         // dp[i][0] 表示第 i 天持有股票的累计最大利润
  5.         // dp[i][1] 表示第 i 天不持有股票，且不处于冷冻期的累计最大利润
  6.         // dp[i][2] 表示第 i 天不持有股票，且处于冷冻期的累计最大利润
  7.         // 这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。
  8.         // 状态转移方程：
  9.         // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
  10.         // dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
  11.         // dp[i][2] = dp[i - 1][0] + prices[i];
  12.         int n = prices.length;
  13.         int[][] dp = new int[n][3];
  14.         dp[0][0] = -prices[0];
  16.         for(int i = 1; i < n; i++) {
  17.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
  18.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
  19.             dp[i][2] = dp[i - 1][0] + prices[i];
  20.         }
  21.         return Math.max(dp[n - 1][1], dp[n - 1][2]);
  22.     }
  23. }