划分型DP
- 给定长度为N的序列活字符串, 要求划分成若干段
- 段数不限, 或者指定K段
- 每一段满足一定的性质
- 做法
- 类似于序列型动态规划, 但是通常要加上段数信息
- 一般用f[i][j]记录前i个元素(元素0 ~ i-1)划分成j段的性质,如最小代价
Leetcode 279 - Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
- Based on the best strategy, we care about the last j ^ 2
- So with the best strategy, n - j^2 must compose with minimum number of perfect squares
- So we need to know the minimum number of perfect squares that compose n - j^2
- We need to get the minimum number of perfect squares that compose n
- Convert to subproblems:
- State: Let's say dp[i] represents the minimum number of perfect squares that compose i
- Transfer equation: dp[i] = min(dp[i - j^2] + 1) where j starts with 1 and 1 <= j^2 <= i
- Initial state: dp[0] = 0
- Calculation sequence: dp[0], dp[1], ..., dp[n]
- return dp[n]
- Time Complexity: N * root(N)
- Space Complexity: N
public int numSquares(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
if (dp[i - j * j] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
}
return dp[n];
}
Leetcode 132 - Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Analysing the problem:
- State: Based on the best strategy, for the last part of string, let's say s[j .. N-1]
- We need to know the minimum of number of cutting for the s[0, ... j-1]
- Subproblem:
We want to know the minimum number of palindrome for the s[0, n-1]We have to know the minimum number of palindrome for the s[0, j-1]
- State transfer equation:
Let's say dp[i] represents the minimum number of palindromes for s[0, i-1]dp[i] = min(dp[j] + 1) where j is in [0, i-1] and s[j .. i-1] is palindrome
- Initial state:
dp[0] = 0
- Calculation sequence: dp[0], dp[1], dp[2], ..., dp[N]
- return dp[N]
- Now we need to know whether a part of string is a palindrome
- There are 2 types of palindrome:
1. length is odd2. length is even
- Assuming we are not looking for palindrome, are are trying to create a palindrome
- We start from the center of string, and expand in two sides, every time add same letter in both sides
- Vice versa, we are looking for a palindrome, assume current letter is center,
- we just expand to two sides, then we can find all palindromes
e.g. s1: p a b c d c b a ts2: p a b c c b a t w
- State transfer equation:
Let's say isPalin[i][j] represents whether s[i..j] is a palindromelength is odd: s[c-1] == s[c+1] -> isPalin[c-1][c+1] = true where c-1 >= 0 and c+1 < lengthlength is even: s[c] == s[c+1] -> isPalin[c][c+1] = true where c >= 0 and c+1 < length
- return isPalin
- The time complexity will be N^2
- The space complexity will be N^2
- Now let's back to question itself
- dp[i] = min(dp[j] + 1) where j is in [0, i-1] and isPalin[j, i-1] = true
- so return dp[N] - 1, cause question is minimum number of partitions
- Therefore, Time Complexity: N ^ 2
- Space Complexity: N ^ 2
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int length = s.length();
int[] dp = new int[length + 1];
boolean[][] isPalin = isPalindromicStr(s);
for (int i = 1; i <= length; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
if (dp[j - 1] != Integer.MAX_VALUE && isPalin[j - 1][i - 1]) {
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[length] - 1;
}
public boolean[][] isPalindromicStr(String s) {
int length = s.length();
boolean[][] isPalin = new boolean[length][length];
isPalin[0][0] = true;
// length is odd
for (int i = 0; i < length; i++) {
isPalin[i][i] = true;
int left = i - 1;
int right = i + 1;
while (left >= 0 && right < length && s.charAt(left) == s.charAt(right)) {
isPalin[left][right] = true;
left--;
right++;
}
}
// length is even
for (int i = 0; i < length; i++) {
int left = i;
int right = i + 1;
while (left >= 0 && right < length && s.charAt(left) == s.charAt(right)) {
isPalin[left][right] = true;
left--;
right++;
}
}
return isPalin;
}
Method 2:
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int length = s.length();
int[] dp = new int[length + 1];
boolean[][] isPalin = isPalindromicStr(s);
for (int i = 1; i <= length; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (isPalin[j][i - 1]) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[length] - 1;
}
public boolean[][] isPalindromicStr(String s) {
int length = s.length();
boolean[][] isPalin = new boolean[length][length];
for (int i = 0; i < length; i++) {
isPalin[i][i] = true;
}
for (int i = 0; i < length - 1; i++) {
isPalin[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int len = 2; len < length; len++) {
for (int start = 0; start + len < length; start++) {
isPalin[start][start + len] = isPalin[start + 1][start + len - 1] &&
(s.charAt(start) == s.charAt(start + len));
}
}
return isPalin;
}
Description
Given n books and the i-th book has pages[i] pages. There are k persons to copy these books.
These books list in a row and each person can claim a continous range of books. For example, one copier can copy the books from i-th to j-th continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).
They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?
Return the shortest time that the slowest copier spends.
The sum of book pages is less than or equal to 2147483647
Have you met this question in a real interview?
Example
Example 1:
Input: pages = [3, 2, 4], k = 2
Output: 5
Explanation:
- First person spends 5 minutes to copy book 1 and book 2.
- Second person spends 4 minutes to copy book 3.
Example 2:
Input: pages = [3, 2, 4], k = 3
Output: 4
Explanation: Each person copies one of the books.
Challenge
O(nk) time
Analysing the problem:
- State: Based on best strategy, assume the last person is Bob(kth person)
- If Bob need to finish books from jth to N-1th
- Then Bob need pages[j] + pages[j + 1] + ... + pages[N-1] mins
- So we need to know the minimum time for fist j-1 books which are done by k-1 people
- If a person finished the books from ith to jth, then it will take pages[i] + .. + pages[j]
- So total consumption time is depended on the time duration for the last person
- If first j-1 books takes Q mins, the last person takes T mins
- So if T < Q, it doesn't matter how long it will be finished for the last person, so it depends on last person
- Thus, we need to find a way that split into no more than k tasks, which makes get the mininum value from all
- maximum time consumption
- Subproblem:
We want to get mininum time consumption to finish N books with k peopleSo we need to know the mininum time consumption for j-1 books with k-1 people- State transfer equation:
- Let's say dp[k][i] represents the mininum time consumption for k people to finish first i books
- So dp[k][i] = min(max(dp[k-1][j], pages[j]+...+pages[i-1])) where j = [0, i]
- Initialization:
- 0 people, 0-N book, dp[0][0] = 0; dp[0][1] = dp[0][1] = .... = dp[0][n] = infinity
- k people, 0 books, dp[0][0] = dp[1][0] .... dp[k][0] = 0
- Calculation sequence: dp[0][0] ... dp[0][n], dp[1][0].....dp[1][n], .....dp[k][n]
- return dp[k][n]
- Time Complexity: kN^2
- Space Complexity: KN -> can be optimized to N
- if K > N -> K = N
public int copyBooks(int[] A, int K) {
if (A == null || A.length == 0 || K == 0) {
return 0;
}
int numOfPages = A.length;
int[][] dp = new int[2][numOfPages + 1];
int old = 0;
int now = 1;
for (int i = 0; i <= numOfPages; i++) {
dp[now][i] = Integer.MAX_VALUE;
}
dp[now][0] = 0;
for (int i = 1; i <= K; i++) {
old = now;
now = 1 - old;
for (int j = 0; j <= numOfPages; j++) {
dp[now][j] = Integer.MAX_VALUE;
int sum = 0;
for (int k = j; k >= 0; k--) {
if (dp[old][k] != Integer.MAX_VALUE) {
dp[now][j] = Math.min(dp[now][j], Math.max(sum, dp[old][k]));
}
if (k > 0) {
sum += A[k - 1];
}
}
}
}
return dp[now][numOfPages];
}
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Example
Example 1:
Input: [3,4,8,5], backpack size=10
Output: 9
Example 2:
Input: [2,3,5,7], backpack size=12
Output: 12
Challenge
O(n x m) time and O(m) memory.
O(n x m) memory is also acceptable if you do not know how to optimize memory.
Analysing the problem:
- State: Based on the best strategy, for the last item, we either can get W from first N-1 items
- Or we can get W-A[N-1] for the first N-1 items, then can get W as well
- Subproblem: We want to know whether we can get W for N items
- We need to know 1. we can get W for the first N-1 items? 2. can we get W-A[N-1] for the first N-1 items
- State transfer equation:
- Let's say dp[i][w] represents whether we can w for the first i items
- dp[i][w] = dp[i - 1][w] | dp[i - 1][w - A[i]] where i >= 1 and w >= A[i]
- Initial state:
dp[0][0] = true, dp[0][1] = dp[0][2] = ... = dp[0][w] = false- Calculation sequence: dp[0][0]....dp[0][N], dp[1][0]...dp[1][N]
- return: from N go backward, if dp[i][w] = true, return w
- Time complexity: NW where N = number of items and W is the weight
- Space complexity: W using rolling array since we only looking previous state
public int backPack(int m, int[] A) {
if (m == 0 || A == null || A.length == 0) {
return 0;
}
int length = A.length;
boolean[][] dp = new boolean[2][m + 1];
int old = 0;
int now = 1;
dp[now][0] = true;
for (int i = 1; i <= length; i++) {
old = now;
now = 1 - old;
for (int w = 0; w <= m; w++) {
dp[now][w] = dp[old][w];
if (w - A[i - 1] >= 0) {
dp[now][w] |= dp[old][w - A[i - 1]];
}
}
}
for (int w = m; w >= 0; w--) {
if (dp[now][w]) {
return w;
}
}
return 0;
}
Method 2:
public int backPack(int m, int[] A) {
if (m == 0 || A == null || A.length == 0) {
return 0;
}
// dp[w] represents while bag can handle w kg, the maximum weight can get
int[] dp = new int[m + 1];
for (int i = 0; i < A.length; i++) {
for (int w = m; w >= 0; w--) {
if (w - A[i] >= 0) {
dp[w] = Math.max(dp[w], dp[w - A[i]] + A[i]);
}
}
}
return dp[m];
}
Summary
- 要求不超过M时拼出的最大重量
- 记录前i个物品能评出那些重量
- 前i个物品能拼出的重量:
- 前i-1个物品能拼出的重量
- 前i-1个物品能拼出的重量 + 第i个物品重量Ai-1
Lintcode 563 - Backpack V
Description
中文
English
Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
Each item may only be used once
Have you met this question in a real interview?
Example
Given candidate items [1,2,3,3,7] and target 7,
A solution set is:
[7]
[1, 3, 3]
return 2
Analysing the problem:
- Based on the best strategy, for the last item, there are two cases
- For the first N-1 items, we have already get w, so return number of first n-1 items to get w
- first N-1 items can get w-nums[N-1], so total number is number of ways to get w-nums[N-1] items
- So total number will be case1 + case2
- Subproblem and state transfer equation:
Let's say dp[i][w] represents the number of ways to get w for first i items
- So dp[i][w] = dp[i-1][w] + dp[i-1][w-nums[i]] where i >= 1 and w - nums[i] >= 0
- Initial state: dp[0][0] = 1, dp[0][1]....dp[0][N] = 0
- Calculation sequence: dp[0][0]...dp[0][1], dp[1][0]...dp[1][n]
- return dp[N][w]
- Time complexity: NW
- Space complexity: NW, using rolling array can optimize to W
public int backPackV(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return target == 0 ? 1 : 0;
}
int length = nums.length;
int[][] dp = new int[2][target + 1];
int old = 0;
int now = 1;
dp[now][0] = 1;
for (int i = 1; i <= length; i++) {
old = now;
now = 1 - old;
for (int w = target; w >= 0; w--) {
dp[now][w] = dp[old][w];
if (w >= nums[i -1]) {
dp[now][w] += dp[old][w - nums[i - 1]];
}
}
}
return dp[now][target];
}
Space can be optimized again
calculation sequence1
that's why we can optimize
public int backPackV(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return target == 0 ? 1 : 0;
}
int length = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= length; i++) {
for (int w = target; w >= 0; w--) {
dp[w] = dp[w];
if (w >= nums[i -1]) {
dp[w] += dp[w - nums[i - 1]];
}
}
}
return dp[target];
}
Leetcode 377 - Combination Sum IV
Description
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
A number in the array can be used multiple times in the combination.
Different orders are counted as different combinations.
Have you met this question in a real interview?
Example
Example1
Input: nums = [1, 2, 4], and target = 4
Output: 6
Explanation:
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
Example2
Input: nums = [1, 2], and target = 4
Output: 5
Explanation:
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
Analysing the problem:
- State: Assume we have nums[0]..nums[n-1] N different numbers
- Based on the best strategy, for the last number, there are two key points:
1. for any correct combination, total sum must be target2. if last number is k, then the sum of previous numbers is target - k
- So if the last number is nums[0], then we want to know number of combination for target - nums[0]
- ....
- last number is nums[N-1], then we want to know number of combination for target - nums[N-1]
- Subproblem and state transfer equation:
Let's say dp[i] number of ways to get i- dp[i] = sum(dp[i - nums[j]]) where j is in [0, n-1] and i >= nums[j]
- Initial state: dp[0] = 1;
- return dp[target]
- Time complexity: NT where N = number of numbers, T = target
- Space complexity: T
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return target == 0 ? 1 : 0;
}
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
背包型DP总结
-
Backpack可行性背包
- 题目要求最多装多少重量
- 记录前i个物品能不能拼出重量w
-
Backpack V, Backpack IV， 计数型背包
- 题目要求有多少种方式装出重量
- Backpack V: 记录前i个物品有多少种方式拼出重量W
- Backpack IV: 记录有多少种方式拼出重量W
- 关键点
- 最后一步
- 最后一个背包内的物品是哪个
- 最后一个物品有没有进背包
- 最后一步
