简单题
509. 斐波那契数/剑指Offer10-I. 斐波那契数列
没有用数列存储, 因为转台转移过程只与前两个值有关.
class Solution {
public int fib(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int pre1 = 1, pre2 = 1, sum = 2;
for (int i = 3; i <= n; i++) {
sum = (pre1 + pre2) % 1000000007;//剑指的题要取余
pre1 = pre2;
pre2 = sum;
}
return sum;
}
}
322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
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 ? -1 : dp[amount];
}
}
这些题如果正向写, 这两道题就是递归. 而递归实际上可以看作是用树去枚举, 时间复杂度是指数级的, 为了简化运算, 就需要带记忆的递归来减少计算. 这不由得会让人想起前序遍历, 而动态规划则是自底向上, 像后序遍历. 做的时候要清楚子问题是什么, 根据最小子问题的条件判断动态规划的迭代方向.
状态转移方程和base case应当是一起想的, 而不是分步骤, 但是知道了状态转移方程之后写代码的时候要先想base case. 状态的数量也要清楚.
子序列
对于子序列问题, 甚至不需要真正把dp数组看成数组, 而是看成抽象的范围. 通过范围的关系解题, 而不是想象数组上一个方向, 左边右边的含义.
300. 最长递增子序列
每一个点和前面的所有点有关, base case是只有一个数, 长度为1.
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length <= 1) return nums.length;
int[] dp = new int[nums.length];
int res = 1;
Arrays.fill(dp, 1);
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
if (dp[i] > res) res = dp[i];
}
}
return res;
}
}
53. 最大子序和/剑指Offer42. 连续子数组的最大和
base case只有一个数, 最大和永远是自己. dp数组代表前面的数到这个数, 最大子序列的和是多少, 也就是可以选择不要前面的序列和(如果前面为负), 或者要前面的序列和, 有点language model的味道. 因为每次计算只与前面的数有关, 所以可以只用两个值来完成计算.
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = Arrays.copyOf(nums, nums.length);
int res = dp[0];
for (int i = 1; i < dp.length; i++) {
if (dp[i] < dp[i - 1] + dp[i]) dp[i] = dp[i - 1] + dp[i];
if (dp[i] > res) res = dp[i];
}
return res;
}
}
5. 最长回文子串
双指针解法较为简单.
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String temp = parlindrome(s, i, i);
res = temp.length() > res.length() ? temp : res;
temp = parlindrome(s, i, i + 1);
res = temp.length() > res.length() ? temp : res;
}
return res;
}
String parlindrome(String str, int i, int j) {
while (i >= 0 && j < str.length() && str.charAt(i) == str.charAt(j)) {
i--;
j++;
}
return str.substring(i + 1, j);
}
}
用dp做, 这是一个单序列用二维数组解的题. base case是单个字母为true, 两个相同的字母也是true. 类似双指针, dp(i,j)=dp(i+1,j-1) and (s(i)=s(j)), 每个状态和左下角的子状态有关.
class Solution {
public String longestPalindrome(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
dp[i][i] = true;
}
int length = 1;
int begin = 0;
for (int i = s.length() - 2; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (j - i == 1 || j - i == 2) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = true;
if (j - i + 1 > length) {
begin = i;
length = j - i + 1;
}
}
} else {
if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
dp[i][j] = true;
if (j - i + 1 > length) {
begin = i;
length = j - i + 1;
}
}
}
}
}
return s.substring(begin, begin + length);
}
}
516. 最长回文子序列
这也是一个单序列用二维数组解的题. 注意序列是可以不连续的, 子串是连续的, 所以这道题实际上简单一点, 只要s.charAt(i) == s.charAt(j), 那么就可以通过左下角的长度计算, 否则只能在左边或者下边选一个最大值.
class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
dp[i][i] = 1;
}
for (int i = s.length() - 2; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] += dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][s.length() - 1];
}
}
单序列用二维数组解, 就把
i和j当成序列的左右边界, 通过这个边界去扩张.题目中的串一般都是指连续的, 而序列是可以不连续的
1143. 最长公共子序列
接下来几道都是一个双序列用二维数组解的题. 递归法:
class Solution {
int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
memo = new int[m][n];
for (int[] row: memo) Arrays.fill(row, -1);
return dp(text1, text2, 0, 0);
}
private int dp(String s1, String s2, int i, int j) {
if (i >= s1.length() || j >= s2.length()) {
return 0;
}
if (memo[i][j] != -1) return memo[i][j];
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = 1 + dp(s1, s2, i + 1, j + 1);
} else {
memo[i][j] = Math.max(dp(s1, s2, i, j + 1), dp(s1, s2, i + 1, j)); //另外一个情况已经包含
}
return memo[i][j];
}
}
自底向上dp法如下, 同递归, 每个子状态只与左, 上, 左上有关. 多加了一行和一列为0的数组, 当做base case.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
583. 两个字符串的删除操作
这道题实际上就是等价于lcs问题. 算出了lcs再根据lcs长度反推即可.
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.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 m + n - 2 * dp[m][n];
}
}
712. 两个字符串的最小ASCII删除和
递归.
class Solution {
int memo[][];
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
memo = new int[m][n];
for (int[] row: memo) {
Arrays.fill(row, -1);
}
return dp(s1, s2, 0, 0);
}
private int dp(String s1, String s2, int i, int j) {
int res = 0;
if (i >= s1.length()) {
while (j < s2.length()) {
res += s2.charAt(j);
j++;
}
return res;
}
if (j >= s2.length()) {
while (i < s1.length()) {
res += s1.charAt(i);
i++;
}
return res;
}
if (memo[i][j] != -1) return memo[i][j];
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, s2, i + 1, j + 1);
} else {
memo[i][j] = Math.min(dp(s1, s2, i, j + 1) + s2.charAt(j), dp(s1, s2, i + 1, j) + s1.charAt(i));
}
return memo[i][j];
}
}
dp. 这里其实可以感受到dp的本质依然是穷举, 二维数组实际上就是列举出了所有的情况. base case是把所有的字母全部删除, 也就是把ascii码累加(最差值). ascii是unicode的子集, 所以这里这么说没问题.
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
}
}
}
return dp[m][n];
}
}
72. 编辑距离
和上一题差不多, 增删改都要计入操作, 增对应上, 删对应左, 改对应左上.
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) dp[i][0] = i;
for (int j = 1; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; 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], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
return dp[m][n];
}
}
要记录用了什么状态就把int替换成包含
int val和int choice的Node即可, 然后倒着推.
背包九讲
题目在acwing2~12.
0-1背包
两个状态, 容量和可选择物品. 选择是是否放进背包. 二维数组j表示当前容量, i表示第前几个物品, 二维数组的内容就表示在前i个物品里面, 价值最大的选择.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
int N = Integer.parseInt(arr[0]), V = Integer.parseInt(arr[1]);
int[][] inputs = new int[N][2];
for (int i = 0; i < N; i++) {
arr = sc.nextLine().split(" ");
inputs[i][0] = Integer.parseInt(arr[0]); //体积
inputs[i][1] = Integer.parseInt(arr[1]); //价值
}
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (inputs[i - 1][0] > j) dp[i][j] = dp[i - 1][j];
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - inputs[i - 1][0]] + inputs[i - 1][1]); //不装or装
}
}
}
System.out.println(dp[N][V]);
}
}
416. 分割等和子集(0-1背包)
如果和为偶数, 那么相当于转换成nums中的数(背包体积)能否组成sum/2大小的数字(总体积).
class Solution {
public boolean canPartition(int[] nums) {
int n = Arrays.stream(nums).sum();
if (n % 2 != 0) return false;
int sum = n / 2;
boolean[][] dp = new boolean[nums.length + 1][sum + 1];
for (int i = 0; i <= nums.length; i++) dp[i][0] = true;
for (int i = 1; i <= nums.length; i++) {
for (int j = 1; j <= sum; j++) {
if (nums[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.length][sum];
}
}
//状态压缩后
class Solution {
public boolean canPartition(int[] nums) {
int n = Arrays.stream(nums).sum();
if (n % 2 != 0) return false;
int sum = n / 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0)
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[sum];
}
}
完全背包
物品数量没有限制. 在0-1背包的基础上, 多考虑当前i重复使用的情况.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
int N = Integer.parseInt(arr[0]), V = Integer.parseInt(arr[1]);
int[][] inputs = new int[N][2];
for (int i = 0; i < N; i++) {
arr = sc.nextLine().split(" ");
inputs[i][0] = Integer.parseInt(arr[0]); //体积
inputs[i][1] = Integer.parseInt(arr[1]); //价值
}
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (inputs[i - 1][0] > j) dp[i][j] = dp[i - 1][j];
else {
dp[i][j] = Math.max(dp[i][j - inputs[i - 1][0]] + inputs[i - 1][1], Math.max(dp[i - 1][j], dp[i - 1][j - inputs[i - 1][0]] + inputs[i - 1][1])); //重复装or不装or新装
}
}
}
System.out.println(dp[N][V]);
}
}
322. 零钱兑换(完全背包)
前面的零钱兑换其实可以用完全背包的思路来. 前面做这道题的时候, 将amount作为大循环的条件, 但是对大多数题来说, 用coins作为大循环条件更好, 防止重叠的情况(我的意思是指考虑到我们做背包问题的遍历顺序来说, 当然二维数组只要遍历顺序改变了也可以达到等效的效果). 这里压缩了维度.
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
518. 零钱兑换II(完全背包)
转换成完全背包问题, 条件有可选择的硬币(背包), 金额总量(容量). 那么i代表前i个硬币, j代表金额. 这里没有压缩维度.
class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length + 1][amount + 1];
for (int i = 0; i <= coins.length; i++)
dp[i][0] = 1;
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
if (j < coins[i - 1]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
}
}
return dp[coins.length][amount];
}
}
多重背包
物品的数量有限制了. 实际上就是0-1背包加了k这个循环. 这里用了状态压缩, j这个维度需要倒过来遍历, 相当于自动地从上一层循环继承了值, 如果超出范围就自动完成了之前的if (inputs[i - 1][0] > j) dp[i][j] = dp[i - 1][j];操作, 并且防止重复计算. 这里不状态压缩的方法我没写出来. 有二进制和单调队列优化方法, 暂跳过.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
int n = Integer.parseInt(arr[0]);
int v = Integer.parseInt(arr[1]);
int[] volumes = new int[n + 1];
int[] values = new int[n + 1];
int[] amounts = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr = sc.nextLine().split(" ");
volumes[i] = Integer.parseInt(arr[0]);
values[i] = Integer.parseInt(arr[1]);
amounts[i] = Integer.parseInt(arr[2]);
}
int[] dp = new int[v + 1];
for (int i = 1; i <= n; i++) {
for (int j = v; j >= 0; j--) {
for (int k = 0; k <= amounts[i] && k * volumes[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * volumes[i]] + k * values[i]);
}
}
}
System.out.print(dp[v]);
}
}
二进制
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
int n = Integer.parseInt(arr[0]);
int v = Integer.parseInt(arr[1]);
List<Integer> volumes = new LinkedList<>();
List<Integer> values = new LinkedList<>();
for (int i = 1; i <= n; i++) {
arr = sc.nextLine().split(" ");
int volume = Integer.parseInt(arr[0]);
int value = Integer.parseInt(arr[1]);
int total = Integer.parseInt(arr[2]);
for (int j = 1; j <= total; j *= 2) {
total -= j;
volumes.add(j * volume);
values.add(j * value);
}
if (total > 0) {
volumes.add(total * volume);
values.add(total * value);
}
}
int[] dp = new int[v + 1];
for (int i = 0; i < volumes.size(); i++) {
for (int j = v; j >= volumes.get(i); j--) {
dp[j] = Math.max(dp[j], dp[j - volumes.get(i)] + values.get(i));
}
}
System.out.print(dp[v]);
}
}
混合背包
结合0-1背包, 完全背包, 多重背包. 我这里都用一维数组演示了, 可以和前三道题对比.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
int N = Integer.parseInt(arr[0]), V = Integer.parseInt(arr[1]);
int[][] inputs = new int[N][3];
for (int i = 0; i < N; i++) {
arr = sc.nextLine().split(" ");
inputs[i][0] = Integer.parseInt(arr[0]); //体积
inputs[i][1] = Integer.parseInt(arr[1]); //价值
inputs[i][2] = Integer.parseInt(arr[2]); //数量
}
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
if (inputs[i][2] == -1) {
for (int j = V; j >= 0; j--) {
if (j < inputs[i][0]) break;
dp[j] = Math.max(dp[j], dp[j - inputs[i][0]] + inputs[i][1]);
}
} else if (inputs[i][2] == 0) {
for (int j = inputs[i][0]; j <= V; j++) { //反过来了就不能用break了, 直接跳过边界条件即可
dp[j] = Math.max(dp[j], dp[j - inputs[i][0]] + inputs[i][1]);
}
} else {
for (int j = V; j >= 0; j--) {
for (int k = 1; k <= inputs[i][2] && inputs[i][0] * k <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - inputs[i][0] * k] + inputs[i][1] * k); //不装or装
}
}
}
}
System.out.println(dp[V]);
}
}
打家劫舍
198. 打家劫舍
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
}
213. 打家劫舍II
等价于在上一道题的基础上, 取[0, nums.length - 1)和[1, nums.length)这两个范围之中的较大值, 因为首尾不能相连.
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(rob(nums, 0, nums.length - 1), rob(nums, 1, nums.length));
}
public int rob(int[] nums, int start, int end) {
int[] dp = new int[end - start + 1];
dp[0] = 0;
dp[1] = nums[start];
int n = dp.length;
for (int i = 2; i < n; i++) {
dp[i] = Math.max(nums[i - 1 + start] + dp[i - 2], dp[i - 1]);
}
return dp[n - 1];
}
}
337. 打家劫舍III
二叉树的后序遍历 + 递归的动态规划. 递归需要记忆化, 时间复杂度$O(n)$.
class Solution {
Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
if (root == null) return 0;
if (memo.containsKey(root)) return memo.get(root);
int yes = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
int no = rob(root.left) + rob(root.right);
int res = Math.max(yes, no);
memo.put(root, res);
return res;
}
}
股票问题
121. 买卖股票的最佳时机
class Solution {
public int maxProfit(int[] prices) {
int min_price = prices[0];
int res = 0;
for (int price: prices) {
if (min_price > price) min_price = price;
if (price - min_price > res) res = price - min_price;
}
return res;
}
}
122. 买卖股票的最佳时机II
最优解法是贪心, 只要当前时间比前面的时间高, 就
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1];
}
return res;
}
}
123. 买卖股票的最佳时机III/188. 买卖股票的最佳时机IV
题意一样, 直接做IV题. dp[i][j][k]表示在第i天, 我们持有股票的状态为j(0代表不持有, 1代表持有), 已经进行了k次交易时能够获取的最大利润.
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if(n <= 1) return 0;
int[][][] dp = new int[n][2][k + 1];
for(int i = 0; i <= k; i++){
dp[0][0][i] = 0;
dp[0][1][i] = -prices[0];
}
for(int i = 1; i < n; i++){
for(int j = 1; j <= k; j++){
dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j] + prices[i]);
dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j - 1] - prices[i]);
}
}
return dp[n - 1][0][k];
}
}
309. 最佳买卖股票时机含冷冻期
dp[i][0]: 持有股票; dp[i][1]: 不持有股票, 处于冷冻期; dp[i][2]: 不持有股票, 不处于冷冻期.
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int[][] dp = new int[prices.length][3];
dp[0][0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
dp[i][1] = dp[i - 1][0] + prices[i]; //当天是冷冻期
dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
}
return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
}
}
714. 买卖股票的最佳时机含手续费
dp[i][1]: 持有股票; dp[i][0]: 不持有股票.
class Solution {
public int maxProfit(int[] prices, int fee) {
int[][] dp = new int[prices.length][2];
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 dp[prices.length - 1][0];
}
}
887. 鸡蛋掉落
带记忆化的递归, 会超时, 但是思路正确. 复杂度是dp函数本身的复杂度$O(n)$, 乘上不同状态组合的总数$O(kn)$.
class Solution {
int[][] dp;
public int superEggDrop(int K, int N) {
dp = new int[K + 1][N + 1];
for (int[] arr: dp) {
Arrays.fill(arr, -1);
}
return dp(K, N);
}
public int dp(int k, int n) {
if (k == 1) return n;
if (n == 0) return 0;
if (dp[k][n] != -1) return dp[k][n];
int res = n;
for (int i = 1; i <= n; i++) {
res = Math.min(res, Math.max(dp(k, n - i), dp(k - 1, i - 1)) + 1);
}
dp[k][n] = res;
return res;
}
}
for (int i = 1; i <= n; i++)这个顺序遍历条件, 可以用二分法来优化, 防止超时. 复杂度$O(KNlogN)$.
class Solution {
int[][] dp;
public int superEggDrop(int K, int N) {
dp = new int[K + 1][N + 1];
for (int[] arr: dp) {
Arrays.fill(arr, -1);
}
return dp(K, N);
}
public int dp(int k, int n) {
if (k == 1) return n;
if (n == 0) return 0;
if (dp[k][n] != -1) return dp[k][n];
int res = n;
// for (int i = 1; i <= n; i++) {
// res = Math.min(res, Math.max(dp(k, n - i), dp(k - 1, i - 1)) + 1);
// }
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
int broken = dp(k - 1, mid - 1);
int unbroken = dp(k, n - mid);
if (broken > unbroken) {
right = mid - 1;
res = Math.min(res, broken + 1);
} else {
left = mid + 1;
res = Math.min(res, unbroken + 1);
}
}
dp[k][n] = res;
return res;
}
}
参考
comments powered by Disqus