动态规划
动态规划
基本步骤
1.明确 base case
2.明确「状态」
3.明确「选择」
4,定义 dp 数组/函数的含义
斐波那契数列(明白什么是重叠子问题)
暴力递归
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
递归树：
暴力递归会导致重复计算，我们可以进行剪枝
public int fib(int N) {
// 备忘录全初始化为 0
int[] memo = new int[N + 1];
// 进行带备忘录的递归
return helper(memo, N);
}
private int helper(int[] memo, int n) {
// base case
if (n == 0 || n == 1) return n;
// 已经计算过，不用再计算了
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
状态压缩：
根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，可以依据此特点做出优化：
int fib(int n) {
if (n < 1) return 0;
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
凑零钱问题(如何列出状态转移方程)
题目：给 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
按照动态规划的步骤来解题：
1、确定 base case，目标金额 amount 为 0 时算法返回 0,amount小于0时说明这种解法不可取，返回-1
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
public int coinChange(int[] coins, int amount) {
// 题目要求的最终结果是 dp(amount)
return dp(coins, amount)
}
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解则跳过
if (subProblem == -1) continue;
// 在子问题中选择最优解，然后加一
res = Math.min(res, subProblem + 1);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
再来消除重叠子问题
int[] memo;
public int coinChange(int[] coins, int amount) {
memo = new int[amount + 1];
// dp 数组全都初始化为特殊值
Arrays.fill(memo, -666);
return dp(coins, amount);
}
private int dp(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
// 查备忘录，防止重复计算
if (memo[amount] != -666)
return memo[amount];
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解则跳过
if (subProblem == -1) continue;
// 在子问题中选择最优解，然后加一
res = Math.min(res, subProblem + 1);
}
// 把计算结果存入备忘录
memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
return memo[amount];
}
背包问题
分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
通过次数188,588提交次数370,341
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这里可以将背包的容量看作数组sum的一半，问可不可以在给定物品的情况下刚好装满背包
class Solution {
int[][] memo;
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;
sum = sum / 2;
memo = new int[nums.length][sum+1];
for(int i = 0;i < nums.length;i++){
Arrays.fill(memo[i],-1);
}
return dp(nums,0,sum);
}
boolean dp(int[] nums,int index,int sum){
if(index == nums.length || sum < 0){
return false;
}
if(memo[index][sum] != -1){
if(memo[index][sum] == 0) return false;
return true;
}
boolean result;
if(sum > 0){
result = dp(nums,index + 1,sum - nums[index]) || dp(nums,index + 1,sum);
if(result) memo[index][sum] = 1;
else memo[index][sum] = 0;
return result;
}
if(sum == 0){
memo[index][sum] = 1;
return true;
}
memo[index][sum] = 0;
return false;
}
}
经典题型
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
通过次数385,154提交次数741,358
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dpTable = new int[nums.length];
Arrays.fill(dpTable,1);
for(int j=1;j<nums.length;j++){
for(int k=0;k<j;k++){
if(nums[k]<nums[j])
dpTable[j] = Math.max(dpTable[j],dpTable[k]+1);
}
}
int result = -1;
for(int i=0;i<dpTable.length;i++){
result = Math.max(result,dpTable[i]);
}
return result;
}
}
int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
public int lengthOfLIS(int[] nums) {
int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要处理的扑克牌
int poker = nums[i];
/***** 搜索左侧边界的二分查找 *****/
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
/*********************************/
// 没找到合适的牌堆，新建一堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
}
下降路径最小和
输入为一个 n * n 的二维数组 matrix，计算从第一行落到最后一行，经过的路径和最小为多少。
函数签名如下：
int minFallingPathSum(int[][] matrix);
使用dfs
class Solution {
int maxColumn;
int maxRow;
int minValue = Integer.MAX_VALUE;
public int minFallingPathSum(int[][] matrix) {
maxColumn = matrix[0].length;
maxRow = matrix.length;
for(int i=0;i<maxColumn;i++)
dfs(matrix,0,i,0);
return minValue;
}
void dfs(int[][] matrix,int row,int column,int value){
if(row<0||row>=maxRow||column<0||column>=maxColumn) return;
if(row == maxRow-1){
minValue = Math.min(value+matrix[row][column],minValue);
}
for(int i=column-1;i<=column+1;i++){
dfs(matrix,row+1,i,value+matrix[row][column]);
}
}
}
//dfs会超时
首先看到dp函数的定义：
int dp(int[][] matrix, int i, int j);
从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。
只要知道到达 (i-1, j), (i-1, j-1), (i-1, j+1) 这三个位置的最小路径和，加上 matrix[i][j] 的值，就能够计算出来到达位置 (i, j) 的最小路径和（加上备忘录与没加备忘录）：
class Solution {
public int minFallingPathSum(int[][] matrix) {
int result = Integer.MAX_VALUE;
for(int j=0;j<matrix[0].length;j++){
result = Math.min(dp(matrix,matrix.length-1,j),result);
}
return result;
}
int dp(int[][] matrix,int i,int j){
if(i<0||j<0||i>=matrix.length||j>=matrix[0].length)
return Integer.MAX_VALUE;
//base case
if(i == 0) return matrix[0][j];
//状态转移
return matrix[i][j]+minInThree(
dp(matrix,i-1,j-1),
dp(matrix,i-1,j),
dp(matrix,i-1,j+1)
);
}
int minInThree(int a,int b,int c){
return Math.min(a,Math.min(b,c));
}
}
//还是会超时
int[][] memo;
int dp(int[][] matrix, int i, int j) {
// 1、索引合法性检查
if (i < 0 || j < 0 ||
i >= matrix.length ||
j >= matrix[0].length) {
return 99999;
}
// 2、base case
if (i == 0) {
return matrix[0][j];
}
// 3、查找备忘录，防止重复计算
if (memo[i][j] != 66666) {
return memo[i][j];
}
// 进行状态转移
memo[i][j] = matrix[i][j] + min(
dp(matrix, i - 1, j),
dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1)
);
return memo[i][j];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
完整实现：
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int res = Integer.MAX_VALUE;
// 备忘录里的值初始化为 66666
memo = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], 66666);
}
// 终点可能在 matrix[n-1] 的任意一列
for (int j = 0; j < n; j++) {
res = Math.min(res, dp(matrix, n - 1, j));
}
return res;
}
// 备忘录
int[][] memo;
int dp(int[][] matrix, int i, int j) {
// 1、索引合法性检查
if (i < 0 || j < 0 ||
i >= matrix.length ||
j >= matrix[0].length) {
return 99999;
}
// 2、base case
if (i == 0) {
return matrix[0][j];
}
// 3、查找备忘录，防止重复计算
if (memo[i][j] != 66666) {
return memo[i][j];
}
// 进行状态转移
memo[i][j] = matrix[i][j] + min(
dp(matrix, i - 1, j),
dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1)
);
return memo[i][j];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
class Solution {
int[][] memo;
public int minFallingPathSum(int[][] matrix) {
int result = Integer.MAX_VALUE;
memo = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
Arrays.fill(memo[i], Integer.MAX_VALUE);
}
for(int j=0;j<matrix[0].length;j++){
result = Math.min(dp(matrix,matrix.length-1,j),result);
}
return result;
}
int dp(int[][] matrix,int i,int j){
if(i<0||j<0||i>=matrix.length||j>=matrix[0].length)
return Integer.MAX_VALUE;
//base case
if(i == 0) return matrix[0][j];
if(memo[i][j] != Integer.MAX_VALUE) return memo[i][j];
memo[i][j] = matrix[i][j]+minInThree(
dp(matrix,i-1,j-1),
dp(matrix,i-1,j),
dp(matrix,i-1,j+1)
);
//状态转移
return memo[i][j];
}
int minInThree(int a,int b,int c){
return Math.min(a,Math.min(b,c));
}
}
编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
def minDistance(s1, s2) -> int:
# 定义：dp(i, j) 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
def dp(i, j):
# base case
#解释一下base case 当某一个单词走完时，要转换的单词对应进行插入若删除即可
if i == -1: return j + 1
if j == -1: return i + 1
if s1[i] == s2[j]:
return dp(i - 1, j - 1) # 啥都不做
else:
return min(
dp(i, j - 1) + 1, # 插入
dp(i - 1, j) + 1, # 删除
dp(i - 1, j - 1) + 1 # 替换
)
# i，j 初始化指向最后一个索引
return dp(len(s1) - 1, len(s2) - 1)
可以用备忘录进行优化
最长上升子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
函数原型：
public int lengthOfLIS(int[] nums) {}
dp数组的定义：
dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
当我们知道dp[0..i]时，就能推出dp[i+1]
就可以痛过nums[i+1]找到nums[0..i]中比nums[i+1]小的数中dp[0..i]最大的就可以得到dp[i+1]的值
int res = 0;
for(int j=0;j<i+1;i++){
if(nums[j]<nums[i+1]){
res = Math.max(res,dp[j]+1);
}
}
而dp[0] == nums[0]
完整代码:
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
提示：
1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104
函数原型：
public int maxEnvelopes(int[][] envelopes) {}
这个是二维的，没有办法用LIS(Longest Increasing Subsequence),但我们有办法把它转变成一个LIS的问题
先将envelopes按照宽度升序排列，如果遇到宽度相同的则按长度降序排列(因为相同宽度的信封是不同互装的，这样做能保证只会子序列只会选择宽度相同的一个信封)
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
//Compare（）比较用来排序的两个参数。根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。
Arrays.sort(envelopes, new Comparator<int[]>()
{
public int compare(int[] a, int[] b) {
return a[0] == b[0] ?
b[1] - a[1] : a[0] - b[0];
}
});
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
最大子数组
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
函数原型：
public int maxSubArray(int[] nums) {}
dp数组的定义：
以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
状态转移方程：
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
完整代码：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
函数原型：
public int longestCommonSubsequence(String text1, String text2) {}
class Solution {
int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
memo = new int[text1.length()][text2.length()];
for(int i=0;i<text1.length();i++)
Arrays.fill(memo[i],Integer.MAX_VALUE);
return dp(text1,0,text2,0);
}
int dp(String text1,int t1,String text2,int t2){
if(t1 == text1.length() || t2 == text2.length()) return 0;
if(memo[t1][t2] != Integer.MAX_VALUE) return memo[t1][t2];
if(text1.charAt(t1) == text2.charAt(t2)){
memo[t1][t2] = 1 + dp(text1,t1+1,text2,t2+1);
}else{
memo[t1][t2] = Math.max(
dp(text1,t1+1,text2,t2),
dp(text1,t1,text2,t2+1)
);
}
return memo[t1][t2];
}
}
最小路径和
很经典的一道使用动态规划+记忆集的一道题
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
通过次数287,504提交次数417,198
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] memo;
public int minPathSum(int[][] grid) {
memo = new int[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++){
Arrays.fill(memo[i],Integer.MAX_VALUE);
}
return dp(grid,grid.length-1,grid[0].length-1);
}
int dp(int[][] grid,int i,int j){
if(i<0 || j<0 || i>= grid.length || j>= grid[0].length)
return Integer.MAX_VALUE;
if(i==0 && j==0) return grid[0][0];
if(memo[i][j] != Integer.MAX_VALUE) return memo[i][j];
memo[i][j] = grid[i][j] + Math.min(dp(grid,i-1,j),dp(grid,i,j-1));
return memo[i][j];
}
}
地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
通过次数39,920提交次数83,071
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dungeon-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] memo;
public int calculateMinimumHP(int[][] dungeon) {
memo = new int[dungeon.length][dungeon[0].length];
for(int i = 0;i<dungeon.length;i++){
Arrays.fill(memo[i],-666);
}
return dp(dungeon,0,0);
}
int dp(int[][] dungeon,int x,int y){
if(x == dungeon.length || y == dungeon[0].length){
return Integer.MAX_VALUE;
}
//base case
if(x == dungeon.length - 1 && y == dungeon[0].length - 1){
return dungeon[x][y] >= 0 ? 1 : -dungeon[x][y] + 1;
}
if(memo[x][y] != -666){
return memo[x][y];
}
int result = -dungeon[x][y] + Math.min(dp(dungeon,x+1,y),dp(dungeon,x,y+1));
memo[x][y] = result > 0 ? result : 1;
return memo[x][y];
}
}
dp函数的定义很重要！我们要做的是定义好这个dp函数然后相信它的定义然后进行状态转移。
如果这道题的dp函数定义为 0，0 到x,y这个点所需要的最小健康值是不对的，因为这时我们进行状态转移所需的信息不够，比如当一个点可以由它的上面那个点或者是左边那个点转移过来，且这俩个点所需要的最小健康值相同，但我们还需要这俩个点的生命值才能知道是否可以转移到xy这个点
所以我们将dp函数定义为x,y 这个点到右下角点所需的最小健康值
鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2：
输入：k = 2, n = 6
输出：3
示例 3：
输入：k = 3, n = 14
输出：4
提示：
1 <= k <= 100
1 <= n <= 104
通过次数53,272提交次数183,261
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] memo;
public int superEggDrop(int k, int n) {
memo = new int[k+1][n+1];
for(int i = 0;i <= k;i++)
Arrays.fill(memo[i],-1);
return dp(k,n);
}
int dp(int k,int n){
if(k == 1) return n;
if(n == 0) return 0;
if(memo[k][n] != -1) return memo[k][n];
int res = Integer.MAX_VALUE;
for(int i = 1;i <= n;i++){
res = Math.min(res,Math.max(
dp(k-1,i-1),
dp(k,n-i)
)+1);
}
memo[k][n] = res;
return res;
}
}
股票买卖问题
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
通过次数617,949提交次数1,077,836
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] dp;
public int maxProfit(int[] prices) {
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]);
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
}
return dp[prices.length-1][0];
}
}
//空间优化版本
class Solution {
int[][] dp;
public int maxProfit(int[] prices) {
// dp = new int[prices.length][2];
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
int dp_i_0 = 0;
int dp_i_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]);
// dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
dp_i_0 = Math.max(dp_i_0,dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1,-prices[i]);
}
// return dp[prices.length-1][0];
return dp_i_0;
}
}
122. 买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
通过次数506,836提交次数732,832
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] dp;
public int maxProfit(int[] prices) {
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]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.length-1][0];
}
}
//空间优化版本
class Solution {
//int[][] dp;
public int maxProfit(int[] prices) {
// dp = new int[prices.length][2];
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
int dp_i_0 = 0;
int dp_i_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]);
//dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp_i_0 = Math.max(dp_i_0,dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1,dp_i_0-prices[i]);
}
// return dp[prices.length-1][0];
return dp_i_0;
}
}
可以发现题目一个题目二一个是要求只能交易一次一个是要求可以交易无限次，其它的条件都是相同的，因此代码也十分相似，仅仅是改变了一行代码
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
这是因为当交易次数限制为1时 dp [i] [1]表示 要在第i天进行一次交易，那么当然第i天以前就没有一天进行过交易，从而dp[i-1] [0] = 0；
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 105
通过次数140,972提交次数260,977
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][][] dp;
public int maxProfit(int[] prices) {
dp = new int[prices.length][3][2];
dp[0][1][0] = 0;
dp[0][2][1] = -prices[0];
dp[0][1][0] = 0;
dp[0][1][1] = -prices[0];
for(int i = 1;i < prices.length;i++){
for(int j = 2;j >= 1;j--){
dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]);
}
}
return dp[prices.length-1][2][0];
}
}
//空间优化版本
class Solution {
// int[][][] dp;
public int maxProfit(int[] prices) {
// dp = new int[prices.length][3][2];
// dp[0][1][0] = 0;
// dp[0][2][1] = -prices[0];
// dp[0][1][0] = 0;
// dp[0][1][1] = -prices[0];
int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
for(int price : prices){
// for(int i = 0;i < prices.length;i++){
// for(int j = 2;j >= 1;j--){
// dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);
// dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]);
dp_i20 = Math.max(dp_i20, dp_i21 + price);
dp_i21 = Math.max(dp_i21, dp_i10 - price);
dp_i10 = Math.max(dp_i10, dp_i11 + price);
dp_i11 = Math.max(dp_i11, -price);
// }
// }
}
return dp_i20;
}
}
188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
通过次数96,680提交次数243,664
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复用以前的代码即可
注意当k > n / 2相当于 k = 无限次的情况
class Solution {
int[][][] dp;
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n <= 0) {
return 0;
}
if (k > n / 2) {
// 交易次数 k 没有限制的情况
return maxProfit_k_inf(prices);
}
dp = new int[prices.length][k+1][2];
// k = 0 时的 base case
for (int i = 0; i < prices.length; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}
for(int i = 0;i < prices.length;i++){
for(int j = k;j >= 1;j--){
if (i == 0) {
dp[i][j][0] = 0;
dp[i][j][1] = -prices[i];
continue;
}
dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]);
}
}
return dp[prices.length-1][k][0];
}
int maxProfit_k_inf(int[] prices){
// dp = new int[prices.length][2];
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
int dp_i_0 = 0;
int dp_i_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]);
//dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp_i_0 = Math.max(dp_i_0,dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1,dp_i_0-prices[i]);
}
// return dp[prices.length-1][0];
return dp_i_0;
}
}
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
通过次数130,589提交次数212,149
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[][] dp;
public int maxProfit(int[] prices) {
dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1;i < prices.length;i++){
if(i == 1){
dp[1][0] = Math.max(dp[0][0],dp[0][1] + prices[1]);
dp[1][1] = Math.max(dp[0][1],-prices[1]);
continue;
}
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-2][0] - prices[i]);
}
return dp[prices.length-1][0];
}
}
//空间优化版本
class Solution {
// int[][] dp;
public int maxProfit(int[] prices) {
// dp = new int[prices.length][2];
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
// for(int i = 1;i < prices.length;i++){
// if(i == 1){
// dp[1][0] = Math.max(dp[0][0],dp[0][1] + prices[1]);
// dp[1][1] = Math.max(dp[0][1],-prices[1]);
// continue;
// }
// 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-2][0] - prices[i]);
// }
// return dp[prices.length-1][0];
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
int dp_pre_0 = 0; // 代表 dp[i-2][0]
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
}
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
提示：
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
通过次数109,514提交次数150,826
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复用无限交易次数的代码+减去手续费的修改即可
class Solution {
//int[][] dp;
public int maxProfit(int[] prices, int fee) {
// dp = new int[prices.length][2];
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
int dp_i_0 = 0;
int dp_i_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]);
dp_i_0 = Math.max(dp_i_0,dp_i_1 + prices[i] - fee);
dp_i_1 = Math.max(dp_i_1,dp_i_0-prices[i]);
}
// return dp[prices.length-1][0];
return dp_i_0;
}
}