背包

01背包

416. 分割等和子集

//f[i][j]表示能否从 nums中前i个 选出一个和恰好等于 j 的子序列.这不就是01背包
f[i][j] = f[i-1][j - nums[i]] || f[i-1][j] 选和不选
01背包优化成一维形式，i维度不要，内层循环从target递减
也可以用记忆化搜索做

class Solution {public boolean canPartition(int[] nums) {//f[i][j]表示能否从 nums中前i个 选出一个和恰好等于 j 的子序列.这不就是01背包//f[i][j] = f[i-1][j - nums[i]] || f[i-1][j] 选和不选//01背包优化成一维形式，i维度不要，内层循环从target递减int n = nums.length;int target = 0;for(int i = 0; i < n; i ++)target += nums[i];if(target % 2 != 0) return false;target /= 2;boolean[] f = new boolean [target+1];f[0] = true;for(int i = 1; i <= n; i ++) {for(int j = target; j >= nums[i-1]; j --) {f[j] = f[j - nums[i-1]] || f[j];}}return f[target];}
}

完全背包

外层是物品(数组)遍历，内层是限制(容量价值)遍历

279. 完全平方数

完全背包问题

class Solution {public int numSquares(int n) {int[] f = new int[n+1];f[1] = 1;  for(int i = 1; i <= n; i ++) {f[i] = i; // 最坏的情况就是每次+1for(int j = 1 ;j <= n; j ++)if(i >= j*j)f[i] = Math.min(f[i], f[i - j*j] + 1);}return f[n];}
}

322. 零钱兑换

也是完全背包问题

for(int i = 1; i <= n; i ++ ) {for(int j = c[i-1]; j <= amount; j ++) {dp[j] = Math.min(dp[j], dp[j-c[i-1]] + 1);}
}

Arrays.fill(dp, amount + 1); //因为是最小值，初始化0会一直是0

class Solution {public int coinChange(int[] c, int amount) {//dp[i]:表示最小个数//dp[j] = min(dp[j], dp[j-c[i]] + 1)int n = c.length;int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1); //因为是最小值，初始化0会一直是0dp[0] = 0;for(int i = 1; i <= n; i ++ ) {for(int j = c[i-1]; j <= amount; j ++) {dp[j] = Math.min(dp[j], dp[j-c[i-1]] + 1);}}int ans = dp[amount];return ans < amount + 1 ? ans : -1;}
}

两个字符串DP

LCR 095. 最长公共子序列

class Solution {public int longestCommonSubsequence(String text1, String text2) {//设 f(i,j)表示第一个字符串的前 i个字符和第二个字符串的前 j个字符的最长公共子序列//dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + 1) 或者 max(dp[i-1][j], dp[i][j-1]）//忽略text1[i]或者忽略text2[j]//这个是 求两个字符串的公共子序列，不需要len 不是遍历len对len分1 2 更长的情况的int n = text1.length(), m = text2.length();int[][] dp = new int [n+1][m+1];int ans = 0;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m; j ++) {if(Objects.equals(text1.charAt(i-1),text2.charAt(j-1))) dp[i][j] = Math.max(Math.max(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1] + 1);else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];//两个字符串的最长公共子序列直接返回f[n][m].因为公共子序列后面的一定比前面的长。但是递增子序列就不一定了}
}

也不一定两个字符串就 设两变量f[i,j]这样

139. 单词拆分

f[i]:前i个能否被拆分【这个问题其实是单个字符串，从set里匹配单个字符串】
如果能找到j<i f[j]=true 并且 s[j~i]在words里面，那么f[i]也能被拆分

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> words = new HashSet<>(wordDict);//f[i]:前i个能否被拆分int n = s.length();boolean[] f = new boolean[n+1];f[0] = true;for(int i = 1; i <= n; i ++) {//如果能找到j f[j]=true 并且 s[j~i]在words里面，那么f[i]也能被拆分for(int j = i-1; j >= 0; j --) { //因为前面都已经匹配了，这样更快if(f[j] && words.contains(s.substring(j, i))) f[i] = true;}}return f[n];}
}

JAVA的substring是开始位置，终止位置。终止位置是开区间不包含他

单个数组字符串DP

5. 最长回文子串

单个数组，dp[i][j] = dp[i+1][j-1] && s[i]==s[j]

遍历len len=2需要特判

class Solution {public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n + 1][n + 1];//dp[i][j]:字符串相关一般都是从i到j//dp[i][j] = dp[i+1][j-1] && s[i]==s[j]int res = 0;String resStr = "";for(int i = 0; i <= n; i ++){dp[i][i] = true;}for(int len = 1; len <= n; len ++) {for(int i = 0; i + len -1 < n; i ++) {int j = i + len -1;if(len == 1) {dp[i][j] = true;}else if(len == 2) {dp[i][j] = s.charAt(i)== s.charAt(j);}else {dp[i][j] = dp[i+1][j-1] && (s.charAt(i)==s.charAt(j)); }if(dp[i][j] && res < len) {res = len; resStr = s.substring(i,j + 1);//substring(int beginIndex, int endIndex) }}}return resStr;}
}

300. 最长递增子序列

单个数组， dp[i] = Math.max(dp[i], dp[j] + 1)

public int lengthOfLIS(int[] nums) {//dp[i]:到i的最长递增子序列//dp[i] = dp[j]+1 int n = nums.length;int[] dp = new int [n+1];int ans = 0;for(int i = 1; i <= n ; i ++ ) {dp[i] = 1;for(int j =1; j <= n; j ++ ) {if(nums[i-1] > nums[j-1]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}ans = Math.max(ans, dp[i]);//位置}return ans;
}

53.最大子数组和

请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

dp[i] = Math.max(dp[i-1], 0) + nums[i]

class Solution {public int maxSubArray(int[] nums) {int dp[] = new int[nums.length+1];int res  = nums[0];dp[0] = Math.max(nums[0],0);for(int i = 1; i < nums.length; i ++) {dp[i] = Math.max(dp[i-1], 0) + nums[i];res = Math.max(res, dp[i]);}return res;}
}

152. 乘积最大子数组

要求连续：

由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin
同时求解当前最大值和当前最小值

由于f[i]只和f[i-1] g[i-1]有关，可用两个变量存

class Solution {public int maxProduct(int[] nums) {int n = nums.length;int ans = Integer.MIN_VALUE;int imax = 1; int imin = 1;for(int i = 1; i <= n; i ++ ) {if(nums[i-1] < 0){ int tmp = imax;imax = imin;imin = tmp;}imax = Math.max(imax * nums[i-1], nums[i-1]);imin = Math.min(imin * nums[i-1], nums[i-1]);ans = Math.max(ans, imax);}return ans;}
}

198. 打家劫舍

要第i家的最大金额：s[i] = u[i-1]+nums[i]; 则一定不要第i-1家
不要第i家的最大金额：u[i]=max(u[i-1], s[i-1]) 也可能不要第i-1家，也可能要

class Solution {public int rob(int[] nums) {//要：s[i] = u[i-1]+nums[i]; 不要u[i]=max(u[i-1], s[i-1])int len = nums.length;int[] s = new int[len], u = new int[len];s[0] = nums[0];u[0] = 0;int ans = s[0];for(int i = 1; i < len; i ++) {s[i] = u[i-1] + nums[i];u[i] = Math.max(u[i-1], s[i-1]);ans = Math.max(ans, s[i]);ans = Math.max(ans, u[i]);}return ans;}
}

三角形

120. 三角形最小路径和

注意两种，只有一条路，j=0和对角线

dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

class Solution {public int minimumTotal(List<List<Integer>> triangle) {//dp[i][j]:到达(i,j)的最小路径和//dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]int n = triangle.size();//边界没处理好int[][] dp = new int[n+1][n+1];for(int i = 1; i <= n; i ++ ) {dp[i][0] = triangle.get(i-1).get(0) + dp[i-1][0];//没有(i-1,j-1)那一条路了for(int j = 1; j <= i; j ++) {if(j == i) dp[i][j] = dp[i-1][j-1] + triangle.get(i-1).get(j-1);//灭有(i-1,j)那条路 对角线else dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i-1).get(j-1);}}int ans = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {ans = Math.min(ans, dp[n][i]);}return ans;}
}

杨辉三角：

贪心

121. 买卖股票的最佳时机

遍历所有天i,对于第i天，记录前i天的最小值minn，结果是max(Prices[i]-minn)

class Solution {public int maxProfit(int[] prices) {int ans = 0;int minn = 100000;for(int i = 0; i < prices.length; i ++) {minn = Math.min(minn, prices[i]);//前i天的最小值也可以ans = Math.max(prices[i]-minn, ans);}return ans;}
}

55. 跳跃游戏

class Solution {public boolean canJump(int[] nums) {//dp[i]:nums[i]之前能跳到的最远距离，含i//跳到dp[i]: i + nums[i]//不跳到dp[i]: dp[i-1] i-1之前能跳的最远距离int[] dp = new int [nums.length + 1];for(int i = 1; i < nums.length; i ++) {//不用管最后一个dp[i] = Math.max(dp[i-1], i + nums[i-1]);if(dp[i] < i + 1) return false;//不用管最后一个，因为dp[i]肯定能跳到他后一个}return true;}
}

贪心做法：
while(i > last && i > last + nums[last]) last++;
if(last == i) return false; 说明i前面没有一个满足 i <= last + nums[last]的---->说明没有跳板能跳到i的

class Solution {public boolean canJump(int[] nums) {for(int i = 1, last = 0; i < nums.length; i ++) {while(i > last && i > last + nums[last])  last++;if(last == i) return false;//说明i前面没有一个满足 i <= last + nums[last]的---->说明没有跳板能跳到i的}return true;}
}

45. 跳跃游戏 II

dp[i]: 跳到nums[i]的最小次数
从i不能跳到last, last++;
从i能跳到last,那么，dp[i]就是dp[last]+1。无论last离i多远

class Solution {public int jump(int[] nums) {//dp[i]: 跳到nums[i]的最小次数int[] dp = new int [nums.length];for(int i = 1, last = 0; i < nums.length; i ++) {//从1开始，dp[0]=0啦,last从0计算dp[1]//从i不能跳到last, last++;//从i能跳到last,那么，dp[i]就是dp[last]+1。无论last离i多远while(i > last && i > last + nums[last])  last ++;dp[i] = dp[last] + 1;}return dp[nums.length-1];}
}

区间问题

763. 划分字母区间

end == i // 当前区间合并完毕
end, start分别存储当前区间的终止位置的最大值，当前区间的起始位置

class Solution {public List<Integer> partitionLabels(String S) {char[] s = S.toCharArray();int n = s.length;int[] last = new int[26];for (int i = 0; i < n; i++) {last[s[i] - 'a'] = i; // 每个字母最后出现的下标}List<Integer> ans = new ArrayList<>();int end = 0, start = 0;// 记录当前这一段的起始位置和终止位置for (int i = 0; i < n; i++) {end = Math.max(end, last[s[i] - 'a']); // 更新当前区间右端点的最大值if (end == i) { // 当前区间合并完毕ans.add(end - start + 1); // 区间长度加入答案start = i + 1; // 下一个区间的左端点. 因为i是一直变的}}return ans;}
}

56. 合并区间

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序List<int[]> res = new ArrayList<>();int l = intervals[0][0], r = intervals[0][1];for(int i = 1; i < intervals.length; i ++) {int newl = intervals[i][0], newr = intervals[i][1];if(newr < r) //包含 continue;else if(newl <= r && newr >= r) {r = newr;}else if(newl > r) {//两段不重叠res.add(new int[]{l,r});l = newl;r = newr;}}// 最后一个合并后的区间需要添加到结果中res.add(new int[]{l, r});// 将 List<int[]> 转换为 int[][] 并返回return res.toArray(new int[res.size()][]);}
}