1. 斐波那契数列/跳台阶/三步问题/变态跳台阶：
https://leetcode-cn.com/problems/fibonacci-number/
https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
https://leetcode-cn.com/problems/three-steps-problem-lcci/
https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
2. 打家劫舍
线性：https://leetcode-cn.com/problems/house-robber/
class Solution { public int rob(int[] nums) { //0和1 if(nums.length == 0){ return 0; } if(nums.length == 1){ return nums[0]; } //dp数组，初始化第一个和第二个 int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0],nums[1]); //不能偷相邻的，从2开始遍历 for(int i=2;i<nums.length;i++){ //dp[0]+dp[2]跟dp[1]比较 dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]); } return dp[nums.length-1]; } }环形：https://leetcode-cn.com/problems/house-robber-ii/
class Solution { public int rob(int[] nums) { //0、1、2的情况 if(nums.length == 0){ return 0; } if(nums.length == 1){ return nums[0]; } if(nums.length == 2){ return Math.max(nums[0],nums[1]); } //分成两个数组：偷第一个和不偷第一个 int[] left = Arrays.copyOfRange(nums,0,nums.length-1); int[] right = Arrays.copyOfRange(nums,1,nums.length); //提取大的结果 return Math.max(MyRob(left),MyRob(right)); } public int MyRob(int[] nums){ //dp数组，初始化dp[0]和dp[1]的值 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]; } }
3. 股票问题：121、122、123、309、714
只购买一次：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
class Solution { public int maxProfit(int[] prices) { if(prices.length == 0){ return 0; } //花费cost和利润 int cost = prices[0]; int profit = 0; //cost取最小，利润取最大 for(int i=1;i<prices.length;i++){ cost = Math.min(prices[i],cost); profit = Math.max(profit,prices[i] - cost); } return profit; } }多次购买：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
class Solution { public int maxProfit(int[] prices) { //利润 int profit = 0; //差值大于0就叠加 for(int i=1;i<prices.length;i++){ int temp = Math.max(prices[i]-prices[i-1],0); profit += temp; } return profit; } }两次购买：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
class Solution { public int maxProfit(int[] prices) { if(prices.length == 0){ return 0; } //dp数组，初始化5种情况：不持股、第一次买入、第一次卖出、第二次买入、第二次卖出 int[][] dp = new int[prices.length][5]; dp[0][0] = 0; dp[0][1] = -prices[i]; dp[0][2] = 0; dp[0][3] = -prices[i]; dp[0][4] = 0; //状态转移 for(int i=1;i<prices.length;i++){ dp[i][0] = dp[i-1][0]; //第一次买入，由前一天不持股买入得到 dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //第一次卖出，由前一天买入今天卖出得到 dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]); //第二次买入，由前一天卖出今天买入得到 dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]); //第二次卖出，由前一天买入今天卖出得到 dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]); } //提取5种结果的最大值 int n = dp.length; return Math.max(Math.max( Math.max(dp[n-1][0],dp[n-1][1]),Math.max(dp[n-1][2],dp[n-1][3]) ),dp[n-1][4]); } }冷冻期：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
class Solution { public int maxProfit(int[] prices) { if(prices.length == 0){ return 0; } //初始化三种状态 int[][] dp = new int[prices.length][3]; //不持股 dp[0][0] = 0; //持股 dp[0][1] = -prices[0]; //冷冻期 dp[0][2] = 0; for(int i=1;i<prices.length;i++){ //不持股，由前一天不持股和冷冻期得到 dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]); //持股，由前一天不持股买入得到 dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //冷冻期，由前一天持股今天卖出得到 dp[i][2] = dp[i-1][1]+prices[i]; } return Math.max(dp[prices.length-1][0],dp[prices.length-1][2]); } }手续费：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
class Solution { public int maxProfit(int[] prices, int fee) { if(prices.length == 0){ return 0; } //初始化两种状态 int[][] dp = new int[prices.length][2]; //卖出 dp[0][0] = 0; //买入 dp[0][1] = -prices[0]; for(int i=1;i<prices.length;i++){ //卖出，需要手续费 dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee); //买入，不需要手续费 dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); } return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]); } }
4. 零钱兑换和背包问题
硬币兑换背包解：https://leetcode-cn.com/problems/coin-change/
class Solution { public int coinChange(int[] coins, int amount) { if(coins.length == 0){ return 0; } //背包，初始化为MAX_VALUE int[] dp = new int[amount+1]; for(int i=1;i<=amount;i++){ dp[i] = Integer.MAX_VALUE; } //外层为金额，内层为数组 for(int i=1;i<=amount;i++){ for(int j=0;j<coins.length;j++){ if(i-coins[j] >= 0 && dp[i-coins[j]] != Integer.MAX_VALUE){ dp[i] = Math.min(dp[i],dp[i-coins[j]]+1); } } } if(dp[amount] != Integer.MAX_VALUE){ return dp[amount]; }else{ return -1; } } }给定硬币金额：直接递减总金额
class Main{ public int GetCoinCount(int N) { N = 1024 - N; int count = 0; while (N > 0) { if (N >= 64) { N -= 64; } else if (N >= 16) { N -= 16; } else if (N >= 4) { N -= 4; } else { N--; } count++; } return count; } }硬币策略：https://leetcode-cn.com/problems/coin-change-2/
class Solution { public int change(int amount, int[] coins) { //背包数组，0个硬币是只有一种策略 int[] dp = new int[amount+1]; dp[0] = 1; //外层为数组，内层为金额，dp[j] = dp[j]+dp[j-coins[i]] for(int i=0;i<coins.length;i++){ for(int j=coins[i];j<=amount;j++){ dp[j] = dp[j] + dp[j-coins[i]]; } } return dp[amount]; } }0-1背包：https://www.acwing.com/problem/content/2/
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //数量 int n = sc.nextInt(); //体积 int v = sc.nextInt(); //重量和价值 int[] weight = new int[num]; int[] value = new int[num]; for(int i=0;i<num;i++){ weight[i] = sc.nextInt(); value[i] = sc.nextInt(); } //背包 int[] dp = new int[v+1]; //外层为数量，内层为体积 for(int i=0;i<num;i++){ //01背包，倒序遍历 for(int j=v;j>=weight[i];j--){ dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i]); } } System.out.println(dp[v]); } }完全背包：https://www.acwing.com/problem/content/3/
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //数量 int num = sc.nextInt(); //体积 int v = sc.nextInt(); int[] weights = new int[num]; int[] values = new int[num]; for(int i=0;i<num;i++){ weights[i] = sc.nextInt(); values[i] = sc.nextInt(); } int[] dp = new int[v+1]; //外层为数量，内层为体积 for(int i=0;i<num;i++){ //完全背包，正序遍历 for(int j=weights[i];j<=v;j++){ dp[j] = Math.max(dp[j],dp[j-weights[i]] + values[i]); } } System.out.println(dp[v]); } }
5. 一维DP
最长上升子序列：https://leetcode-cn.com/problems/longest-increasing-subsequence/
class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0){ return 0; } //初始化dp数组，tian'cho int[] dp = new int[nums.length]; Arrays.fill(dp,1); int result = 0; for(int i=0;i<nums.length;i++){ //搜索i前面的，如果i比前面的大，更新dp[i] for(int j=0;j<i;j++){ if(nums[i] > nums[j]){ dp[i] = Math.max(dp[i],dp[j]+1); } } //提取结果 result = Math.max(dp[i],result); } return result; } }整数分割/剪绳子：https://leetcode-cn.com/problems/integer-break/
class Solution { public int integerBreak(int n) { int result = 1; //比4小 if(n < 4){ return n-1; } //比4大，分割出3 while(n > 4){ n -= 3; result *= 3; } return result*n; } }把数字翻译成字符串：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
class Solution { public int translateNum(int num) { //转化成字符串 String str = String.valueOf(num); //dp数组。0和1个数只有一种翻译方式 int[] dp = new int[str.length()+1]; dp[0] = 1; dp[1] = 1; //从2个数开始 for(int i=2;i<=str.length();i++){ //截取前两位 String temp = str.substring(i-2,i); //和10比，大于等于0，和25比，小于等于0 if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0){ dp[i] = dp[i-1] + dp[i-2]; }else{ dp[i] = dp[i-1]; } } return dp[str.length()]; } }等差数列划分：https://leetcode-cn.com/problems/arithmetic-slices/comments/
单词拆分：https://leetcode-cn.com/problems/word-break
class Solution { public boolean wordBreak(String s, List<String> wordDict) { //Set去重 Set<String> set = new HashSet<>(wordDict); //dp数组 boolean[] dp = new boolean[s.length()+1]; dp[0] = true; //类似最长上升子序列 for(int i=1;i<=s.length();i++){ //从i往前搜 for(int j=0;j<i;j++){ //如果j为true并且set含有从j到i的字符串，dp[i]为true，break if(dp[j] && set.contains(s.substring(j,i))){ dp[i] = true; break; } } } return dp[s.length()]; } }
6. 二维DP
最大矩形：https://leetcode-cn.com/problems/maximal-rectangle/
class Solution { public int maximalRectangle(char[][] matrix) { if(matrix.length == 0 || matrix[0].length == 0){ return 0; } //初始化dp数组，当矩阵为1时，dp数组第一行初始为1，下面的行叠加 int[][] dp = new int[matrix.length][matrix[0].length]; for(int i=0;i<matrix.length;i++){ for(int j=0;j<matrix[0].length;j++){ if(matrix[i][j] == '1'){ if(i == 0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i-1][j] + 1; } } } } int result = 0; //遍历dp数组 for(int i=0;i<dp.length;i++){ for(int j=0;j<dp[0].length;j++){ //dp数组为0时，跳过 if(dp[i][j] == 0){ continue; } //提取当前值作为高 int curHigh = dp[i][j]; //从j往左搜索，当dp[i][k]不为0 for(int k=j;k>=0 && dp[i][k] != 0;k--){ //min保证行高不变 curHigh = Math.min(curHigh,dp[i][k]); //宽为j-k+1，计算面积 int width = j - k + 1; result = Math.max(curHigh*width,result); } } return result; } }编辑距离：https://leetcode-cn.com/problems/edit-distance/
class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length()+1][word2.length()+1]; //初始化第一行：word1为空，需要进行word2.length()次添加 for(int i=1;i<=word2.length();i++){ dp[0][i] = dp[0][i-1]+1; } //初始化第一列：word2为空，需要进行word1.length()次删除 for(int i=1;i<=word1.length();i++){ dp[i][0] = dp[i-1][0] + 1; } //从[1,1]开始 for(int i=1;i<=word1.length();i++){ for(int j=1;j<=word2.length();j++){ //当字符相同时，等于左上角，否则提取左、上、坐上的最小值 if(word1.charAt(i-1) == word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1; } } } return dp[word1.length()][word2.length()]; } }不同路径：https://leetcode-cn.com/problems/unique-paths/
class Solution { public int uniquePaths(int m, int n) { //初始化dp数组 int[][] dp = new int[m][n]; //直接进行叠加 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ //第一行或第一列，初始为1，内部进行叠加，叠加左和上 if(i==0 || j==0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; } }不同路径：https://leetcode-cn.com/problems/unique-paths-ii/
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int row = obstacleGrid.length; int col = obstacleGrid[0].length; int[][] dp = new int[row][col]; //初始化第一行，遇到障碍物，设置为0，break，否则为1 for(int i=0;i<dp[0].length;i++){ if(obstacleGrid[0][i] == 1){ dp[0][i] = 0; break; }else{ dp[0][i] = 1; } } //初始化第一列，遇到障碍物，设置为0，break，否则为1 for(int i=0;i<dp.length;i++){ if(obstacleGrid[i][0] == 1){ dp[i][0] = 0; break; }else{ dp[i][0] = 1; } } //内部，从[1,1]开始 for(int i=1;i<dp.length;i++){ for(int j=1;j<dp[0].length;j++){ //矩阵值为1，dp为0，否则叠加左和上 if(obstacleGrid[i][j] == 1){ dp[i][j] = 0; }else{ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[row-1][col-1]; } }最大正方形：https://leetcode-cn.com/problems/maximal-square/
class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length == 0 || matrix[0].length == 0){ return 0; } int[][] dp = new int[matrix.length][matrix[0].length]; int side = 0; for(int i=0;i<matrix.length;i++){ for(int j=0;j<matrix[0].length;j++){ //矩阵为1才进行计算 if(matrix[i][j] == '1'){ //第一行和第一列，dp为1，否则提取左、上、左上的最小值 if(i == 0 || j == 0){ dp[i][j] = 1; }else{ dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1; } //提取边长 side = Math.max(side,dp[i][j]); } } } return side*side; } }
最小路径和/礼物最大价值：https://leetcode-cn.com/problems/minimum-path-sum/
class Solution { public int minPathSum(int[][] grid) { if(grid.length == 0 || grid[0].length == 0){ return 0; } for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ //左上角，继续，第一行，叠加左边，第一列，叠加上班，内部，提取左和上的最小值叠加 if(i == 0 && j == 0){ continue; }else if(i == 0){ grid[i][j] = grid[i][j-1] + grid[i][j]; }else if(j == 0){ grid[i][j] = grid[i-1][j] + grid[i][j]; }else{ grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j]; } } } return grid[grid.length-1][grid[0].length-1]; } }最长公共子序列：https://leetcode-cn.com/problems/longest-common-subsequence/
class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] dp = new int[text1.length()+1][text2.length()+1]; //从[1,1]开始 for(int i=1;i<=text1.length();i++){ for(int j=1;j<=text2.length();j++){ //如果两个字符串的字符相同，左上角+1，否则提取左和上的最大值 if(text1.charAt(i-1) == text2.charAt(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]); } } } return dp[text1.length()][text2.length()]; } }最长回文子序列：https://leetcode-cn.com/problems/longest-palindromic-subsequence/
class Solution { public int longestPalindromeSubseq(String s) { //类型：二维转一维 //思路：先将s字符串逆序，转换为最长公共子序列问题 StringBuilder temp = new StringBuilder(s); String r = temp.reverse().toString(); int[][] dp = new int[s.length()+1][r.length()+1]; for(int i=1;i<=s.length();i++){ for(int j=1;j<=r.length();j++){ if(s.charAt(i-1) == r.charAt(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]); } } } return dp[s.length()][r.length()]; } }
俄罗斯套娃：https://leetcode-cn.com/problems/russian-doll-envelopes/
class Solution { public int maxEnvelopes(int[][] envelopes) { if(envelopes.length == 0 || envelopes[0].length == 0){ return 0; } //根据env[0]升序排序，转化为最长上升子序列问题 Arrays.sort(envelopes,(a,b) -> (a[0] - b[0])); //填充dp数组为1 int[] dp = new int[envelopes.length]; Arrays.fill(dp,1); int result = 0; for(int i=0;i<envelopes.length;i++){ for(int j=0;j<i;j++){ //从i往前搜，比前面的大，dp[j]+1 if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){ dp[i] = Math.max(dp[i],dp[j]+1); } } result = Math.max(dp[i],result); } return result; } }
京公网安备 11010502036488号