2020-02-14 DP - 4 - 划分型DP & 博弈型D

2020-02-16 本文已影响0人边走边看边遗忘

划分型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 odd
```
- ```
 2. 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 t 
```
```
         s2:  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 palindrome

 length is odd: s[c-1] == s[c+1] -> isPalin[c-1][c+1] = true where c-1 >= 0 and c+1 < length

 length 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;
    }

Lintcode 437 - Copy Books

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 people

 So 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:
- 1. 0 people, 0-N book, dp[0][0] = 0; dp[0][1] = dp[0][1] = .... = dp[0][n] = infinity
- 1. 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];
    }

Lintcode 92 - Backpack

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
- 1. For the first N-1 items, we have already get w, so return number of first n-1 items to get w
- 1. 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 target

 2. 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
关键点
- 最后一步
  - 最后一个背包内的物品是哪个
  - 最后一个物品有没有进背包

2020-02-14 DP - 4 - 划分型DP & 博弈型D

划分型DP

Summary

背包型DP总结

猜你喜欢

热点阅读