509、斐波那契数
class Solution { public int fib(int n) { // 方法一：递归 // if(n==0){ // return 0; // }else if(n==1){ // return 1; // }else{ // return fib(n-1)+fib(n-2); // } // 方法二：动态规划 if(n<=1) return n; int[] dp = new int[2]; dp[0] = 0; dp[1] = 1; int sum = 0;; for(int i = 2; i <= n; i++){ sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return dp[1]; }}70、爬楼梯
class Solution { public int climbStairs(int n) { if(n==1) return n; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}746、使用最小花费爬楼梯
class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length + 1]; dp[0] = 0; dp[1] = 0; for(int i = 2; i <= cost.length; i++){ dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]); } return dp[cost.length]; }}62、 不同路径
class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = 1; for(int i = 1; i < m; i++){ dp[i][0] = 1; } for(int j = 1; 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]; }}63、不同路径 II
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; if(obstacleGrid[0][0] == 1){ return 0; }else{ dp[0][0] = 1; } for(int i = 1; i < m; i++){ if(obstacleGrid[i][0] == 1){ break; }else{ dp[i][0] = 1; } } for(int j = 1; j < n; j++){ if(obstacleGrid[0][j] == 1){ break; }else{ dp[0][j] = 1; } } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ if(obstacleGrid[i][j] == 1){ continue; }else{ dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }}343、整数拆分
class Solution { public int integerBreak(int n) { // 方法一：贪心 // if(n == 2){ // return 1; // }else if(n == 3){ // return 2; // } // int result = 1; // while(n > 0){ // if(n > 4){ // result *= 3; // n = n - 3; // }else if(n == 4){ // result *= 4; // break; // }else if(n == 3 || n == 2){ // result *= n; // break; // } // } // return result; // 方法二：动态规划 int[] dp = new int[n + 1]; dp[2] = 1; for(int i = 3; i <= n; i++){ for(int j = 1; j <= i - j; j++){ dp[i] = Math.max(dp[i],Math.max(j*(i - j),j*dp[i - j])); } } return dp[n]; }}96、不同的二叉搜索树
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; i++){ for(int j = 1; j <= i; j++){ dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; }}416、分割等和子集
class Solution { public boolean canPartition(int[] nums) { int sum = 0; for(int i = 0; i < nums.length; i++){ sum += nums[i]; } if(sum%2==1){ return false; }else{ sum = sum/2; } Arrays.sort(nums); int[][] dp = new int[nums.length][sum + 1]; for(int i = nums[0]; i <= sum; i++){ dp[0][i] = nums[0]; } for(int i = 1; i < nums.length; i++){ for(int j = 1; j j){ dp[i][j] = dp[i - 1][j]; }else{ dp[i][j] = Math.max(dp[i - 1][j], nums[i] + dp[i - 1][j - nums[i]]); } } } return dp[nums.length - 1][sum] == sum; }}1049、最后一块石头的重量 II
class Solution { public int lastStoneWeightII(int[] stones) { int target = 0; for(int i : stones){ target += i; } int sum = target/2; int[][] dp = new int[stones.length][sum + 1]; for(int i = stones[0]; i <= sum; i++){ dp[0][i] = stones[0]; } for(int i = 1; i < stones.length; i++){ for(int j = 1; j <= sum; j++){ if(j < stones[i]){ dp[i][j] = dp[i - 1][j]; }else{ dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]); } } } return target - 2 * dp[stones.length - 1][sum]; }}494、目标和
class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for(int i:nums){ sum += i; } if(Math.abs(target) > sum) return 0; if((sum + target) % 2 == 1) return 0; int bageSize = (sum + target) / 2; int[] dp = new int[bageSize + 1]; dp[0] = 1; for(int i = 0; i = nums[i]; j--){ dp[j] += dp[j - nums[i]]; } } return dp[bageSize]; }}474、一和零
class Solution { public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; for(String str : strs){ int zeroNum = 0; int oneNum = 0; for(char c: str.toCharArray()){ if(c == '0'){ zeroNum++; }else{ oneNum++; } } for(int i = m; i >= zeroNum; i--){ for(int j = n; j >= oneNum; j--){ dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; }}518、 零钱兑换 II
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for(int i = 0; i < coins.length; i++){ for(int j = coins[i]; j <= amount; j++){ dp[j] += dp[j - coins[i]]; } } return dp[amount]; }}377、组合总和 Ⅳ
class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for(int i = 1; i <= target; i++){ for(int j = 0; j = nums[j]){ dp[i] += dp[i - nums[j]]; } } } return dp[target]; }}322、零钱兑换
class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; for(int i = 0; i < dp.length; i++){ dp[i] = max; } dp[0] = 0; for(int i = 0; i <= amount; i++){ for(int j = 0; j = coins[j] && dp[i - coins[j]] != max){ dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]); } } } return dp[amount]==max?-1:dp[amount]; }}279、完全平方数
class Solution { public int numSquares(int n) { // 创建物品 int length = (int)Math.floor(Math.sqrt(n)); int[] nums = new int[length]; for(int i = 0; i < length; i++){ nums[i] = (i + 1) * (i + 1); } int[] dp = new int[n + 1]; int max = Integer.MAX_VALUE; for(int j = 0; j < dp.length; j++){ dp[j] = max; } dp[0] = 0; for(int i = 0; i < nums.length; i++){ for(int j = nums[i]; j <= n; j++){ dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1); } } return dp[n]; }}139、单词拆分
class Solution { public boolean wordBreak(String s, List wordDict) { HashSet set = new HashSet(wordDict); boolean[] valid = new boolean[s.length() + 1]; valid[0] = true; for(int i = 1; i <= s.length(); i++){ for(int j = 0; j < i && !valid[i]; j++){ if(set.contains(s.substring(j, i)) && valid[j]){ valid[i] = true; } } } return valid[s.length()]; }}198、打家劫舍
class Solution { public int rob(int[] nums) { if(nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(dp[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]; }}213、打家劫舍 II
class Solution { public int rob(int[] nums) { if(nums.length == 1) return nums[0]; return Math.max(robAction(nums, 0, nums.length - 2), robAction(nums, 1, nums.length - 1)); } public int robAction(int[] nums, int start, int end){ if(start == end) return nums[start]; int[] dp = new int[nums.length]; dp[start] = nums[start]; dp[start + 1] = Math.max(dp[start], nums[start + 1]); for(int i = start + 2; i <= end; i++){ dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[end]; }}337、打家劫舍 III
class Solution { public int rob(TreeNode root) {// 后序遍历 int[] res = robAction(root); return Math.max(res[0], res[1]); } public 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; }}121、买卖股票的最佳时机
class Solution { public int maxProfit(int[] prices) { int len = prices.length; if(len == 1) return 0; int[][] dp = new int[len][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for(int i = 1; i < len; i++){ dp[i][0] = Math.max(dp[i - 1][0], -prices[i]); dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]); } return dp[len - 1][1]; }}122、买卖股票的最佳时机 II
class Solution { public int maxProfit(int[] prices) { // 贪心 // int max = 0; // for(int i = 1; i prices[i - 1]){ // max += prices[i] - prices[i - 1]; // } // } // return max; // 动态规划 int len = prices.length; if(len == 1) return 0; int[][] dp = new int[len][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for(int i = 1; i < len; i++){ dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]); dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]); } return dp[len - 1][1]; }}123、买卖股票的最佳时机 III
class Solution { public int maxProfit(int[] prices) { int len = prices.length; int[][] dp = new int[len][5]; dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for(int i = 1; i < len; i++){ dp[i][1] = Math.max(-prices[i], dp[i - 1][1]); dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]); dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]); dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]); } return dp[len - 1][4]; }}188、买卖股票的最佳时机 IV
class Solution { public int maxProfit(int k, int[] prices) { int len = prices.length; int[][] dp = new int[len][1 + 2 * k]; for(int i = 1; i < 1 + 2 * k; i = i + 2){ dp[0][i] = -prices[0]; } for(int i = 1; i < len; i++){ for(int j = 1; j < 1 + 2 * k; j++){ if(j == 1){ dp[i][j] = Math.max(-prices[i], dp[i - 1][1]); }else if(j%2==0){ dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]); }else{ dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]); } } } return dp[len - 1][2 * k]; }}309、最佳买卖股票时机含冷冻期
class Solution { public int maxProfit(int[] prices) { int len = prices.length; if(len == 1) return 0; int[][] dp = new int[len][4]; dp[0][0] = -prices[0]; for(int i = 1; i < len; i++){ dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i]); dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]); dp[i][2] = dp[i - 1][0] + prices[i]; dp[i][3] = dp[i - 1][2]; } return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3])); }}714、买卖股票的最佳时机含手续费
class Solution { public int maxProfit(int[] prices, int fee) { // 贪心 // if(prices.length==1){ // return 0; // } // int index = prices[0]+fee; // int sum=0; // for(int i = 1; i index){ // sum+=prices[i]-index; // index=prices[i]; // }else if(prices[i]+fee<index){ // index=prices[i]+fee; // } // } // return sum; // 动态规划 int len = prices.length; if(len == 1) return 0; int[][] dp = new int[len][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for(int i = 1; i < len; i++){ dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]); dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]); } return Math.max(dp[len - 1][1],dp[len - 1][0]); }}300、最长递增子序列
class Solution { public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp,1); int result = 1; for(int i = 1; i < nums.length; i++){ for(int j = 0; j nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1); } if(dp[i] > result) result = dp[i]; } return result; }}674、最长连续递增序列
class Solution { public int findLengthOfLCIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp,1); int result = 1; int index = 0; for(int i = 1; i = 0; j--){ if(index result) result = dp[i]; } return result; }}718、最长重复子数组
class Solution { public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j result) result = dp[i][j]; } } return result; }}1143、最长公共子序列
class Solution { public int longestCommonSubsequence(String text1, String text2) { char[] nums1 = text1.toCharArray(); char[] nums2 = text2.toCharArray(); int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j result) result = dp[i][j]; } } return result; }}1035、不相交的线
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j result) result = dp[i][j]; } } return result; }}53、最大子数组和
class Solution { public int maxSubArray(int[] nums) { // 贪心 // if(nums.length == 1){ // return nums[0]; // } // int count = 0; // int sum = Integer.MIN_VALUE; // for(int i = 0; i < nums.length; i++){ // count += nums[i]; // sum = Math.max(sum, count); // if(count <= 0){ // count = 0; // } // } // return sum; // 动态规划 int[] dp = new int[nums.length]; dp[0] = nums[0]; int result = nums[0]; for(int i = 1; i result ? dp[i] : result; } return result; }}392、 判断子序列
class Solution { public boolean isSubsequence(String s, String t) { char[] nums1 = s.toCharArray(); char[] nums2 = t.toCharArray(); int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j result) result = dp[i][j]; } } return result == s.length(); }}115、不同的子序列
class Solution { public int numDistinct(String s, String t) { char[] nums1 = s.toCharArray(); char[] nums2 = t.toCharArray(); int[][] dp = new int[nums1.length + 1][nums2.length + 1]; for(int i = 0; i < nums1.length; i++){ dp[i][0] = 1; } for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j <= nums2.length; j++){ if(nums1[i - 1] == nums2[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; }else{ dp[i][j] = dp[i - 1][j]; } } } return dp[nums1.length][nums2.length]; }}583、两个字符串的删除操作
class Solution { public int minDistance(String word1, String word2) { char[] nums1 = word1.toCharArray(); char[] nums2 = word2.toCharArray(); int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j result) result = dp[i][j]; } } return word1.length() + word2.length() - 2 * result; }}72、编辑距离
class Solution { public int minDistance(String word1, String word2) { char[] nums1 = word1.toCharArray(); char[] nums2 = word2.toCharArray(); int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int result = 0; for(int i = 0; i <= nums1.length; i++){ dp[i][0] = i; } for(int i = 0; i <= nums2.length; i++){ dp[0][i] = i; } for(int i = 1; i <= nums1.length; i++){ for(int j = 1; j <= nums2.length; j++){ if(nums1[i - 1] == nums2[j - 1]){ dp[i][j] = dp[i - 1][j - 1]; }else{ dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;; } } } return dp[nums1.length][nums2.length]; }}647、回文子串
class Solution { public int countSubstrings(String s) { boolean[][] dp = new boolean[s.length()][s.length()]; for(int i = s.length() - 1; i >= 0; i--){ for(int j = i; j < s.length(); j++){ if(s.charAt(i) == s.charAt(j)){ if(j - i < 3){ dp[i][j] = true; }else{ dp[i][j] = dp[i + 1][j - 1]; } }else{ dp[i][j] = false; } } } int count = 0; for (int i = 0; i < s.length(); i++) { for (int j = 0; j < s.length(); j++) { if (dp[i][j]) count++; } } return count; }}516、最长回文子序列
class Solution { public int longestPalindromeSubseq(String s) { int[][] dp = new int[s.length() + 1][s.length() + 1]; int result = 1; for(int i = s.length() - 1; i >= 0; i--){ dp[i][i] = 1; for(int j = i + 1; j dp[i][j] ? result : dp[i][j]; } } return result; }}739、每日温度
class Solution { public int[] dailyTemperatures(int[] temperatures) { int lens = temperatures.length; int[] res = new int[lens]; Stack stack = new Stack(); stack.push(0); for(int i = 1; i < lens; i++){ if(temperatures[i] temperatures[stack.peek()]){ int temp = stack.pop(); res[temp] = i - temp; } stack.push(i); } } return res; }}496、下一个更大元素 I
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int lens = nums1.length; int[] res = new int[lens]; Arrays.fill(res,-1); Stack stack = new Stack(); HashMap hashMap = new HashMap(); for (int i = 0 ; i< nums1.length ; i++){ hashMap.put(nums1[i],i); } stack.push(0); for(int i = 1; i < nums2.length; i++){ if(nums2[i] nums2[stack.peek()]){ if (hashMap.containsKey(nums2[stack.peek()])){ Integer index = hashMap.get(nums2[stack.peek()]); res[index] = nums2[i]; } stack.pop(); } stack.push(i); } } return res; }}503、下一个更大元素 II
class Solution { public int[] nextGreaterElements(int[] nums) { int lens = nums.length; int[] res = new int[lens]; Arrays.fill(res,-1); Stack stack = new Stack(); stack.push(0); for(int i = 1; i < 2*lens; i++){ if(nums[i%lens] nums[stack.peek()]){ int temp = stack.pop(); res[temp] = nums[i%lens]; } stack.push(i%lens); } } return res; }}[42]
[84]