注意：本题dp数组就是一个长度为2的数组！ 

/**  * 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) {         //后序遍历         //dp数组是一个长度为2的数组         //0：不偷该节点 1：偷该节点         int[] dp = new int[2];         dp = robAction(root);         return Math.max(dp[0],dp[1]);     }     private int[] robAction(TreeNode root){         int[] res = new int[2];         if(root==null){             return res;         }         int[] left = robAction(root.left);         int[] right = robAction(root.right);         //不偷节点，左右子节点分别取最大的         res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);         //偷节点，左右子节点都不能偷         res[1] = root.val+left[0]+right[0];         return res;     } }

四、股票系列  

详见：代码随想录打卡-股票问题-CSDN博客

五、子序列系列

5.1 最长递增子序列

300.最长递增子序列

注意：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

           初始化：全部为1，只要有一个数字，长度就为1开始（这里利用到了Arrays.fill()方法）

class Solution {     public int lengthOfLIS(int[] nums) {         //dp[i]表示以nums[i]结尾的最长递增子序列         int[] dp = new int[nums.length];         Arrays.fill(dp,1);         int res = 1;          for(int i = 0;i

class Solution {     public int findLengthOfLCIS(int[] nums) {         //动态规划         int[] dp = new int[nums.length];         Arrays.fill(dp,1);         int res = 1;         for(int i = 1;inums[i-1]){                 dp[i] = dp[i-1]+1;             }             res = Math.max(res,dp[i]);         }         return res;     } }

class Solution {     public int findLength(int[] nums1, int[] nums2) {         int[][] dp = new int[nums1.length+1][nums2.length+1];         int res = 0;         for(int i = 1;i

class Solution {     public int longestCommonSubsequence(String text1, String text2) {         //不要求连续         char[] ch1 = text1.toCharArray();         char[] ch2 = text2.toCharArray();         int[][] dp = new int[ch1.length+1][ch2.length+1];         int res = 0;         for(int i = 1;i

class Solution {     public int maxUncrossedLines(int[] nums1, int[] nums2) {         //问题转换：不连续、公共         int[][] dp = new int[nums1.length+1][nums2.length+1];         int res = 0;         for(int i = 1;i

class Solution {     public int maxSubArray(int[] nums) {         //连续         int[] dp = new int[nums.length];         dp[0] = nums[0];         int res = nums[0];         for(int i = 1;i

class Solution {     public int countSubstrings(String s) {         char[] ch = s.toCharArray();         boolean[][] dp = new boolean[ch.length][ch.length];         int res = 0;//记录回文字符数         //已默认初始化，dp为false         for(int i = ch.length-1;i>=0;i--){             for(int j = i;j

class Solution {     public int longestPalindromeSubseq(String s) {         char[] ch = s.toCharArray();         int[][] dp = new int[ch.length][ch.length];         for(int i = ch.length-1;i>=0;i--){             //初始化             dp[i][i] = 1;             for(int j = i+1;j