动态规划
动态规划重点
- 最优子结构
- 边界条件
- 状态转移方程
-
无后效性，即动态规划中的每一个元素(
dp[i],dp[i][j]) 都是final(java的final)的为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
做算法的一个心得
想到最简单最粗暴的方法，不要觉得不合适，先往这个思路去写，也许会豁然开朗想到更好的。
70爬楼梯
详情
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
题解
这题其实非常简单，就是斐波那契数列，但也是最基本的动态规划算法。 f(1) = 1 f(2) = 2 f(n) = f(n-1) + f(n-2) 当n>=3时;
递归，比较慢因为没有剪枝，有许多重复计算
class Solution {
public int climbStairs(int n) {
if(n<=2){
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}
比较直观的dp方法，可以完全看到上述的等式
class Solution {
public int climbStairs(int n) {
if(n<=2){
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];
}
}
迭代方法，斐波那契数列，其实已经是降维的动态规划了
public int climbStairs(int n) {
if(n <= 2){
return n;
}
int a = 1;
int b = 2;
for (int i = 3; i <= n; i++) {
int tmp = a;
a = b;
b = a + tmp;
}
return b;
}
买卖股票
题目详情
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
题解
- dp[i] 0-i中的最小买入价格
- dp[i] = Min(dp[i-1], prices[i]);
/**
*
* @param prices
* @return
*/
public int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfile = 0;
for (int i = 1; i < prices.length; i++) {
int profile = prices[i] - minPrice;
maxProfile = Math.max(profile, maxProfile);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfile;
}
122买卖股票2
详情
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
题解
其实没啥区别，只不过dp[i]记录最小价格时做了一些改动分为做交易和不做交易两种。
public int maxProfit(int[] prices) {
int[] dp = new int[prices.length];
dp[0] = prices[0];
int maxProfile = 0;
for (int i = 1; i < prices.length; i++) {
int curProfile = prices[i] - dp[i - 1];
if(curProfile > 0){
//做这次交易
dp[i] = prices[i];
maxProfile += curProfile;
} else {
//不做这次交易
dp[i] = Math.min(dp[i-1], prices[i]);
}
}
return maxProfile;
}
变量替换
public int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfile = 0;
for (int i = 1; i < prices.length; i++) {
int curProfile = prices[i] - minPrice;
if(curProfile > 0){
//做这次交易
minPrice = prices[i];
maxProfile += curProfile;
} else {
//不做这次交易
minPrice = Math.min(minPrice, prices[i]);
}
}
return maxProfile;
}
思路更简单的贪心算法，只需要后二天比前一天价格便宜就执行买入卖出
public int maxProfit(int[] prices) {
int maxProfile = 0;
for (int i = 0; i < prices.length - 1; i++) {
if (prices[i + 1] > prices[i]) {
maxProfile += prices[i + 1] - prices[i];
}
}
return maxProfile;
}
309买卖股票含冷冻期
题目概述
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
题解
- 2.5维的动态规划题目，股票题目到现在真正需要用到动态规划思想的题目
- 说是2.5维其实
dp状态转移：
- 多状态dp，当日完成后的状态
dp[i][0]当前持有股票的最大收益dp[i][1]当前不持有股票，且不在冷静期的最大收益dp[i][2]当前不持有股票，且在冷静期的最大收益dp[i][0] = Max(dp[i-1][0], dp[i-1][1] - prices[i])昨天有股票 + 今天买入dp[i][1] = Max(dp[i-1][1], dp[i-1][2])昨天不持有股票中的最大值dp[i][2] = dp[i-1][0] + prices[i]昨天持有股票，且今天卖出
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][3];
dp[0][0] = -prices[0];
dp[0][1] = 0;
//虽然不存在这个情况，但只能是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][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
}
5最长回文子串
详情
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。
题解
中心拓展法 从回文的定义出发，从sc[i]出发遍历aba型和abba型，直到不满足，其实就是直观的暴力算法
时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public String longestPalindrome(String s) {
if (null == s || s.length() < 2) {
return s;
}
char[] sc = s.toCharArray();
int start = 0;
int end = 0;
for (int i = 0; i < sc.length; i++) {
//aba型
int l1 = extend(sc, i, i);
//abba型
int l2 = extend(sc, i, i + 1);
int l = Math.max(l1, l2);
if (l > end - start + 1) {
start = i - (l - 1) / 2;
end = i + l / 2;
}
}
return s.substring(start, end + 1);
}
private int extend(char[] sc, int l, int r) {
while (l >= 0 && r < sc.length && sc[l] == sc[r]){
l--;
r++;
}
return r - l - 1;
}
}
动态规划法（说实话我觉得这个动态规划法有点强行，不是很好用）
boolean[][] dp, dp[i][j]代表从i-j是否为回文字符串。- 按照回文的定义
dp[i][i] = true;dp[i][i+1] = s[i] == s[i+1]- 状态转移方程：
dp[i][j] = dp[i-1][j+1] && s[i] == s[j]
- 同时在遍历的过程中记录最大长度和最大的开始/结束。
- 注意遍历顺序：按子串长度遍历，不然会出现
dp[i][j]依赖的dp[i-1][j+1]还是初始化的false - 该
dp[i][j]只是暂存i-j是否为回文，并没有保存结果，更像一个备忘录，整个过程还是上述的中心拓展法。 - 时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public String longestPalindrome(String s) {
if (null == s || s.length() < 2) {
return s;
}
int max = 1;
int st = 0;
int ed = 0;
char[] sc = s.toCharArray();
boolean[][] dp = new boolean[sc.length][sc.length];
//sc[i]必是回文
for (int i = 0; i < sc.length; i++) {
dp[i][i] = true;
}
//从len=2开始
for (int len = 2; len <= sc.length; len++) {
//判断从0开始len长度的是否为回文
for (int i = 0; i <= sc.length - len; i++) {
int j = i + len - 1;
if (len == 2) {
//如果len==2不能用状态转移方程，直接比对
dp[i][j] = sc[i] == sc[j];
} else {
//状态转移
dp[i][j] = dp[i + 1][j - 1] && sc[i] == sc[j];
}
//最大判断
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1;
st = i;
ed = j;
}
}
}
//返回
return s.substring(st, ed + 1);
}
}
Manacher 算法
略…要明确刷题目标，用不到就不看了
53最大子数组和
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
题解
暴力计算所有子串和，看似dp，其实是暴力解法，内存超出限制。有许多小于最大值的数据其实不需要存
dp[i][j]代表i-j长度中的最大的子数组和- 边界
dp[i][i] = nums[i]; - 状态转移
dp[i][j] = dp[i][j-1] + dp[i][j] - 暴力计算所有子串和
- 按长度遍历
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length < 2) {
return nums[0];
}
int max = Integer.MIN_VALUE;
int[][] dp = new int[nums.length][nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i][i] = nums[i];
if(nums[i] > max){
max = nums[i];
}
}
for (int len = 2; len <= nums.length; len++) {
for (int i = 0; i <= nums.length - len; i++) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + nums[j];
if(dp[i][j] > max){
max = dp[i][j];
}
}
}
return max;
}
}
上种解法超出内存限制，一维化，但时间复杂度没变，证明这个动态规划的思路有问题
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length < 2) {
return nums[0];
}
int max = Integer.MIN_VALUE;
int[] dp = new int[nums.length];
for (int len = 1; len <= nums.length; len++) {
for (int i = 0; i <= nums.length - len; i++) {
int j = i + len - 1;
dp[i] += nums[j];
if(dp[i] > max){
max = dp[i];
}
}
}
return max;
}
}
转变思路
- dp[i] = 0 - i元素中最后一个元素是nums[i]的最大的子数组和（这一步是最关键的）
- dp[i] = Max(dp[i-1] + nums[i], nums[i]);
- 这个dp数组的定义实际上就是无后效性的一种了，像我上面的
dp[i][j]也是无后效性的，而如果dp[i]定义为包含nums[i]的最大的子数组和，我们实际上不知道这个可选范围是从哪里到哪里。
/**
* @param nums
* @return
*/
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
}
return Arrays.stream(dp).max().getAsInt();
}
顺序的一维的动态规划可以简化为一个临时变量。
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int cur = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = cur > 0 ? cur + nums[i] : nums[i];
if (cur > max) {
max = cur;
}
}
return max;
}
总结
初观的第一个思路其实是这样
dp[i][j]为i-j中最大的子数组和- 但这样状态转移方程写不出来了，我并不知道
dp[i][j]和dp[i][j-1]之间的关系，于是采取了如下的伪动态规划 - 其实细想后续的动态规划算法分析中的有后效性元素其实就是最早这个二维dp的
dp[0][i]，一样也是有后效性的，我并不知道dp[i]和dp[i-1]的关系 - 转变思路很重要 dp[i] 为0开始最后一个元素为nums[i]的最大字数组和。
55跳跃游戏
概述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
解答
暴力法，从第一步开始能跳的都设置一下。
public boolean canJump(int[] nums) {
boolean[] canJump = new boolean[nums.length];
canJump[0] = true;
for (int i = 0; i < nums.length; i++) {
if (!canJump[i]) {
continue;
}
for (int j = i + 1; j < nums.length && j <= i + nums[i]; j++) {
canJump[j] = true;
}
}
return canJump[nums.length - 1];
}
简单思路：如果一个位置能够到达，那么这个位置左侧所有位置都能到达。
public boolean canJump(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
if(i > max){
return false;
}
max = Math.max(max, i + nums[i]);
if(max >= nums.length - 1){
return true;
}
}
return false;
}
62. 不同路径
详情
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 7 输出：28
题解
动态规划
dp[i][j]为到该格子有几条路- 边界
dp[0][0],dp[i][0],dp[0][j]= 1 - 状态转移
dp[i][j] = dp[i-1][j] + dp[i][j-1]
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
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];
}
排列组合（实际运行数字大会溢出）
- m,n
- 向下m-1步，向右n-1步，总步数m + n - 2
- 从m + n - 2中选出n - 1
public long uniquePaths(int m, int n) {
if(m <= 1 || n <= 1){
return 1;
}
return (int) factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1);
}
private long factorial(int n) {
if (n == 1) {
return 1;
}
return factorial(n - 1) * n;
}
64 最小路径和
题目详情
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
题解
动态规划，和上一题没啥区别
public int minPathSum(int[][] grid) {
if (grid.length < 1) {
return 0;
}
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
for (int i = 1; i < grid.length; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < grid[0].length; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[grid.length - 1][grid[0].length - 1];
}
152. 乘积最大子数组
题目详情
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
题目解答
这不就和最大子数组和一样么，其实不一样，+ 和 * 的区别
正负分开讨论
dp[i][0]为最后一个元素是nums[i]的最大正乘积dp[i][1]为最后一个元素是nums[i]的最大负乘积- 加入还是另起
dp[i][0] = max(dp[i-1][0]*nums[i], nums[i]);nums[i]正dp[i][0] = dp[i-1][1]*nums[i]; nums[i]负dp[i][1] = min(dp[i-1][0]*nums[i], nums[i]); nums[i]负dp[i][1] = dp[i-1][1] * nums[i]; nums[i]正
public int maxProduct(int[] nums) {
int[][] dp = new int[nums.length][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
if(nums[i] > 0){
dp[i][0] = Math.max(dp[i-1][0]*nums[i], nums[i]);
dp[i][1] = dp[i-1][1] * nums[i];
} else {
dp[i][0] = dp[i-1][1]*nums[i];
dp[i][1] = Math.min(dp[i-1][0]*nums[i], nums[i]);
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int tmpMax = Math.max(dp[i][0],dp[i][1]);
if(tmpMax > max){
max = tmpMax;
}
}
return max;
}
概念转换与优化，转变成最大值和最小值
public int maxProduct(int[] nums) {
int[][] dp = new int[nums.length][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i][0] = Math.max(dp[i-1][1]*nums[i], Math.max(dp[i-1][0]*nums[i], nums[i]));
dp[i][1] = Math.min(dp[i-1][1]*nums[i], Math.min(dp[i-1][0]*nums[i], nums[i]));
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, dp[i][0]);
}
return max;
}
最简化
public int maxProduct(int[] nums) {
int lastMax = nums[0];
int lastMin = nums[0];
int actualMax = nums[0];
for (int i = 1; i < nums.length; i++) {
int tmpMax = Math.max(lastMin * nums[i], Math.max(lastMax * nums[i], nums[i]));
int tmpMin = Math.min(lastMin * nums[i], Math.min(lastMax * nums[i], nums[i]));
lastMax = tmpMax;
lastMin = tmpMin;
if (lastMax > actualMax) {
actualMax = lastMax;
}
}
return actualMax;
}
279. 完全平方数
题目详情
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
输入：n = 13 输出：2 解释：13 = 4 + 9
题目解答
动态规划
dp[i] = min(dp[i - j* j]);
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
int tmp = dp[i - j * j] + 1;
if (tmp < min) {
min = tmp;
}
}
dp[i] = min;
}
return dp[n];
}
300. 最长递增子序列
题目解释
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
题目解答
- dp[i] 以nums[i]为终点的最大长度
- dp[i] = nums[i-j] < nums[nums[i]] ? max(dp[i-j]+ 1)
O(n^2)
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
int maxNum = 1;
for (int j = 0; j < i; j++) {
if(nums[i] <= nums[j]){
continue;
}
if(dp[j] + 1 > maxNum){
maxNum = dp[j] + 1;
}
}
dp[i] = maxNum;
}
return Arrays.stream(dp).max().getAsInt();
}
另一种O(nlog(n))的解法，tail[i]是i长度递增子串的最小尾数。
/**
* 7 8 9 1 2 3 4 5
* 7 8 9 -> 1 8 9 -> 1 2 9 -> 1 2 3 -> 1 2 3 4
* @return
*/
public int lengthOfLIS(int[] nums) {
int[] tail = new int[nums.length];
int result = 0;
for (int num : nums) {
int i = 0, j = result;
//二分查找该元素应该放置的位置
while (i < j) {
int m = i + (j - i) / 2;
if(tail[m] < num){
i = m + 1;
} else {
j = m;
}
}
tail[i] = num;
//如果j没动，等于放在了tail[j]的位置
if(j == result){
result++;
}
}
return result;
}
198打家劫舍
题目详情
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
题解
- dp[i] 偷了i的最大值
- dt[i] 不偷i的最大值
- dp[i] = dt[i-1] + nums[i]
- dt[i] = max(dp[i-1], dt[i-1]);
public int rob(int[] nums) {
int[] dp = new int[nums.length];
int[] dt = new int[nums.length];
dp[0] = nums[0];
dt[0] = 0;
for (int i = 1; i < nums.length; i++) {
dp[i] = dt[i - 1] + nums[i];
dt[i] = Math.max(dp[i - 1], dt[i - 1]);
}
return Math.max(dt[nums.length - 1], dp[nums.length - 1]);
}
更简单的思路，上述实际上等dt[i-1] = dp[i-2];
- dp[i] 最大值
- dp[i] 为偷了i-2 + 今天偷了，与偷了i-1之间的最大值
- dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
public int rob(int[] nums) {
if(nums.length < 2){
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 - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
顺序dp的空间优化
public int rob(int[] nums) {
if(nums.length < 2){
return nums[0];
}
int lastTwo = nums[0];
int last = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int tmpLastTwo = lastTwo;
lastTwo = last;
last = Math.max(tmpLastTwo + nums[i], last);
}
return last;
}
221最大正方形
题目详情
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]] 输出：4
相当复杂的方法，O(n^3)
- dp[i][j] 为以i,j为终点的最大正方形边长
- dp[i][j] = 0, 当matrix = ‘0’
- dp[i][j] = dp[i-1][j-1] + 1; 当matrix[i][j] = ‘1’，遍历找到最大边长。
public int maximalSquare(char[][] matrix) {
int max = Integer.MIN_VALUE;
int[][] dp = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
dp[i][0] = isOne(matrix[i][0]) ? 1 : 0;
max = Math.max(max, dp[i][0]);
}
for (int j = 0; j < matrix[0].length; j++) {
dp[0][j] = isOne(matrix[0][j]) ? 1 : 0;
max = Math.max(max, dp[0][j]);
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (!isOne(matrix[i][j])) {
dp[i][j] = 0;
} else if (dp[i - 1][j - 1] > 0) {
dp[i][j] = max(dp, i, j);
} else {
dp[i][j] = 1;
}
max = Math.max(max, dp[i][j]);
}
}
return max * max;
}
private boolean isOne(char c) {
return c == '1';
}
private int max(int[][] dp, int i, int j) {
int last = dp[i - 1][j - 1];
int maxUp = 0;
int maxLeft = 0;
int k = j - 1;
while (k >= j - last && maxUp < last) {
if(dp[i][k] <= 0){
break;
}
k--;
maxUp++;
}
k = i - 1;
while (k >= i - last && maxLeft < last) {
if(dp[k][j] <= 0){
break;
}
k--;
maxLeft++;
}
return Math.min(maxUp, maxLeft) + 1;
}
更好的状态转移方程
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
public int maximalSquare(char[][] matrix) {
int max = Integer.MIN_VALUE;
int[][] dp = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
dp[i][0] = isOne(matrix[i][0]) ? 1 : 0;
max = Math.max(max, dp[i][0]);
}
for (int j = 0; j < matrix[0].length; j++) {
dp[0][j] = isOne(matrix[0][j]) ? 1 : 0;
max = Math.max(max, dp[0][j]);
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (!isOne(matrix[i][j])) {
dp[i][j] = 0;
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
max = Math.max(max, dp[i][j]);
}
}
return max * max;
}
private boolean isOne(char c) {
return c == '1';
}
322 零钱兑换
题目详情
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
O(mn)的方法：
- dp[i] i的钱最少有几种
- dp[i] = min(dp[i-coins] + 1) 遍历每一个coin
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = -1;
}
for (int i = 1; i <= amount; i++) {
int min = Integer.MAX_VALUE;
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
if (i == coin) {
dp[i] = 1;
break;
}
int last = dp[i - coin];
if (last != -1) {
min = Math.min(min, dp[i - coin] + 1);
dp[i] = min;
}
}
}
return dp[amount];
}
边界值优化，思路和上面一样
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
}
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
377打家劫舍2
简单递归，超时，其实也是后序遍历，只不过有种情况需要遍历两次。O(nlogn)
public int rob(TreeNode root) {
return Math.max(doRob(root, true), doRob(root, false));
}
private int doRob(TreeNode node, boolean chooseThis) {
if (null == node) {
return 0;
}
if (null == node.left && null == node.right) {
return chooseThis ? node.val : 0;
}
if(chooseThis){
int left = doRob(node.left, false);
int right = doRob(node.right, false);
return left + right + node.val;
} else {
int left = Math.max(doRob(node.left, false), doRob(node.left, true));
int right = Math.max(doRob(node.right, false), doRob(node.right, true));
return left + right;
}
}
加入备忘录的算法，只需遍历1次，时间复杂度O(n)
private Map<TreeNode, Integer> dp = new HashMap<>();
//不选当前节点的所有子树和
private Map<TreeNode, Integer> dt = new HashMap<>();
public int rob(TreeNode root) {
post(root);
return Math.max(dp.getOrDefault(root, 0), dt.getOrDefault(root, 0));
}
/**
* 选择遍历方式，后序，因为左子树右子树的结果确定后，当前节点的结果才确定
* 找到一个无后效性的dp，
* @return
*/
private void post(TreeNode root){
if(null == root){
return;
}
post(root.left);
post(root.right);
//do this;
//选当前节点
int choice = dt.getOrDefault(root.left, 0) + dt.getOrDefault(root.right, 0) + root.val;
dp.put(root, choice);
//不选当前节点
int left = Math.max(dt.getOrDefault(root.left, 0), dp.getOrDefault(root.left, 0));
int right = Math.max(dt.getOrDefault(root.right, 0), dp.getOrDefault(root.right, 0));
int noChoice = left + right;
dt.put(root, noChoice);
}
把1优化下，一次性返回选当前和不选当前的，也是一次后序遍历
public int rob(TreeNode root) {
int[] rs = doRob(root);
return Math.max(rs[0], rs[1]);
}
/**
* 0 为选了当前
* 1 为没选的
* @param node
* @return
*/
private int[] doRob(TreeNode node) {
if (null == node) {
return new int[2];
}
int[] left = doRob(node.left);
int[] right = doRob(node.right);
int choice = left[1] + right[1] + node.val;
int noChoice = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{choice, noChoice};
}
备注
实际上解决该问题的关键还是在如何找到无后效性的dp子结构
338. 比特位计数
题目详情
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
输入：n = 2 输出：[0,1,1] 解释： 0 –> 0 1 –> 1 2 –> 10
题目解答
其实就是找规律
- dp[i] = 个数
- dp[i] = dp[i-1] + 1; i 奇数
- dp[i] = dp[i/2]; i 偶数
/**
* 0 --> 0
* 1 --> 1 1
* 2 --> 10 1
* 3 --> 11 2
* 4 --> 100 1
* 5 --> 101 2
* 6 --> 110 2
* 7 --> 111 3
* 8 --> 1000 1
* 9 --> 1001 2
* 10 --> 1010 2
*
* @param n
* @return
*/
public int[] countBits(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = (i & 1) == 1 ? dp[i - 1] + 1 : dp[i / 2];
}
return dp;
}
416. 分割等和子集
题目详情
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
题目解答
- 转化为等和子集和=sum/2，即找到一个子集的和 = sum/2，这一步很顺畅
- 但在写findSumSubset方法时遇到了难处，假定的dp[i] i出现的次数，在计算dp[i+1]时无法得到正确的结果，因为该dp是不确定的，不知道之前那个dp[2]到底用了nums里哪些元素。
- 二维dp
dp[i][j]是否存在0-i个元素中，子数组和=jdp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j] j >= nums[i]dp[i][j] = dp[i-1][j]
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
//奇数不可能
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
return findSumSubset(nums, target);
}
/**
* dp[i][j] 是否存在0-i个元素中，子数组和=j
* dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j] j >= nums[i]
* dp[i][j] = dp[i-1][j]
*
* @param nums
* @param target
* @return
*/
private boolean findSumSubset(int[] nums, int target) {
boolean[][] dp = new boolean[nums.length][target + 1];
//dp[i][0] == 0;
for (int i = 0; i < nums.length; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
for (int j = 1; j <= target; j++) {
if (j < num) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j];
}
}
}
return dp[nums.length - 1][target];
}
顺序交替优化
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
//奇数不可能
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
return findSumSubset(nums, target);
}
private boolean findSumSubset(int[] nums, int target) {
boolean[] dp = new boolean[target + 1];
dp[0] = true;
dp[nums[0]] = true;
for (int i = 1; i < nums.length; i++) {
for (int j = target; j > 0; j--) {
if (j >= nums[i]) {
dp[j] = dp[j - nums[i]] || dp[j];
}
}
}
return dp[target];
}
647. 回文子串
题目详情
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
题目解答
暴力中心拓展法
public int countSubstrings(String s) {
int count = 0;
char[] sc = s.toCharArray();
for (int i = 0; i < sc.length - 1; i++) {
//奇数
count += cycle(sc, i, i);
//偶数
count += cycle(sc, i, i + 1);
}
count += cycle(sc, sc.length - 1, sc.length - 1);
return count;
}
private int cycle(char[] sc, int i, int j) {
int c = 0;
while (i >= 0 && j < sc.length && sc[i] == sc[j]) {
i--;
j++;
c++;
}
return c;
}
