阅读量:0
一、动态规划基础
1.1 动态规划：斐波那契数
class Solution { public int fib(int n) { if(n<=1){ return n; } int[] dp = new int[n+1]; //初始化 dp[0] = 0; dp[1] = 1; for(int i = 2;i<n+1;i++){ dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } }1.2 动态规划：爬楼梯
class Solution { public int climbStairs(int n) { if(n<3){ return n; } int[] dp = new int[n+1]; //初始化 dp[1] = 1; dp[2] = 2; for(int i = 3;i<n+1;i++){ dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } }1.3 动态规划：使用最小花费爬楼梯1
class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length+1]; //从0、1开始都不用钱 for(int i = 2;i<cost.length+1;i++){ dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.length]; } }1.4 动态规划：不同路径
class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; //初始化 for(int i = 0;i<m;i++){ dp[i][0] = 1; } for(int j = 0;j<n;j++){ dp[0][j] = 1; } for(int i = 1;i<m;i++){ for(int j = 1;j<n;j++){ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } }1.5 动态规划：不同路径还不够，要有障碍！
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; //初始化，为0：只有一条路，路上还有障碍 //初始化，为1：只有一条路，路上无障碍 for(int i = 0;i<m && obstacleGrid[i][0]==0;i++){ dp[i][0] = 1; } for(int j = 0;j<n && obstacleGrid[0][j]==0;j++){ dp[0][j] = 1; } for(int i = 1;i<m;i++){ for(int j = 1;j<n;j++){ if(obstacleGrid[i][j]==1){ //遇到障碍 dp[i][j] = 0; }else{ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; } }1.6 动态规划：整数拆分，你要怎么拆？
※
class Solution { public int integerBreak(int n) { int[] dp = new int[n+1]; //初始化 dp[2] = 1; for(int i = 3;i<n+1;i++){ //j往后加也是重复 for(int j = 1;j<=i;j++){ dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j])); } } return dp[n]; } }1.7 动态规划：不同的二叉搜索树(opens new window)
※
class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; //初始化 dp[0] = 1; dp[1] = 1; for(int i = 2;i<n+1;i++){ for(int j = 1;j<=i;j++){ //j为头节点，左子树上总元素个数为j-1，总共i个元素，则右子树要减去左子树和头节点，为i-j dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }二、背包问题系列
三、打家劫舍系列
class Solution { public int rob(int[] nums) { if(nums==null || nums.length==0){ return 0; } if(nums.length==1){ return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0],nums[1]); for(int i = 2;i<nums.length;i++){ dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]); } return dp[nums.length-1]; } }注意： Arrays.copyOfRange()方法会返回一个新的数组，其中包含原始数组 original 中从索引 from 到 to-1（不包含to）的元素
class Solution { public int rob(int[] nums) { if(nums==null || nums.length<1){ return 0; } if(nums.length==1){ return nums[0]; } return Math.max(robAction(Arrays.copyOfRange(nums,0,nums.length-1)),robAction(Arrays.copyOfRange(nums,1,nums.length))); } private int robAction(int[] nums){ int pre = 0,cur = 0,tmp; for(int i = 0;i<nums.length;i++){ tmp = cur; cur = Math.max(cur,pre+nums[i]); pre = tmp; } return cur; } }注意：本题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; } }四、股票系列
五、子序列系列
5.1 最长递增子序列
注意：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<nums.length;i++){ for(int j = 0;j<i;j++){ if(nums[j]<nums[i]){ dp[i] = Math.max(dp[i],dp[j]+1); } res = Math.max(res,dp[i]); } } return res; } }5.2 最长连续递增序列
注意：与上题的区别在于，这题要求连续
class Solution { public int findLengthOfLCIS(int[] nums) { //动态规划 int[] dp = new int[nums.length]; Arrays.fill(dp,1); int res = 1; for(int i = 1;i<nums.length;i++){ if(nums[i]>nums[i-1]){ dp[i] = dp[i-1]+1; } res = Math.max(res,dp[i]); } return res; } }5.3 最长重复子数组
注意：这里要求是连续的，所以不相等时的dp[i][j]不需要考虑了
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<nums1.length+1;i++){ for(int j = 1;j<nums2.length+1;j++){ if(nums1[i-1]==nums2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; } res = Math.max(res,dp[i][j]); } } return res; } }5.4 最长公共子序列
注意：与上题区别是，本题不要求连续，故不相等的情况也要考虑
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<ch1.length+1;i++){ for(int j = 1;j<ch2.length+1;j++){ if(ch1[i-1]==ch2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } res = Math.max(res,dp[i][j]); } } return res; } }5.5 不相交的线
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<nums1.length+1;i++){ for(int j = 1;j<nums2.length+1;j++){ if(nums1[i-1]==nums2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } res = Math.max(res,dp[i][j]); } } return res; } }5.6 最大子数组和
注意：连续。并且要明确dp[i]的概念，是包含了i为下标的数的，所以要么是nums[i]加上前面的和，要么就是单独nums[i]，也就是以nums[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<nums.length;i++){ //看是加上前面的大，还是以这个数为起点大 dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); res = Math.max(res,dp[i]); } return res; } }5.7 编辑距离问题
详见：https://blog.csdn.net/supercool7/article/details/140353805?spm=1001.2014.3001.5502
5.8 回文子串
注意：本题要求连续，故只要已经不是回文，后面再加也一定不是回文了
注意遍历顺序需要根据推导顺序来
布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false
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<ch.length;j++){ if(ch[i]==ch[j]){ if(j-i<=1 || dp[i+1][j-1]){ //由于本题要求是连续，所以若已经不是回文，直接为默认值false即可，不需要再推导，后面都是false res++; dp[i][j] = true; } } } } return res; } }5.9 最长回文子序列
注意：与上题的区别是，本题不要求连续！
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<ch.length;j++){ if(ch[i]==ch[j]){ dp[i][j] = dp[i+1][j-1]+2; }else { dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]); } } } return dp[0][ch.length-1]; } }