动态规划4 划分型动态规划

题目1：LintCode 108 Palindrome Partitioning II

题目2：LintCode 108 Palindrome Partitioning II

Input: "aab"
Output: 1
Explanation: Split "aab" once, into "aa" and "b", both palindrome.

将字符串每一段划分成字符串最少划分几次      划分最少，也就是回文串最长

确定状态：

最后一段回文串S[j..N-1]  需要知道S前j个字符串S[0..j-1]最少可以划分成几个字符串

dp[i]:设S前i个字符最少爱可以划分成几个字符串

最后一个回文串长度至少是1，所有j是从0到i-1

　　　　　　　　假设：最后是一段回文串

dp[i] = min{dp[j]+1}  | S[j..i-1]是回文串     区间    [0, 1, 2,   j ... i-1, i] 

　　　j=0..i-1

dp[0] = 0;空串可以被分成0个回文串

怎么判断回文串:

• 奇数   中轴外，左右两边都一样
• 偶数   左右两边都一样

以每个子串为中心向两边扩展     时间复杂度 0(n^2)

用isPalin[i][j]:表示s[i,j]是否是回文串 

dp[i] = min{dp[j]+1}  | S[j..i-1]是回文串    ====> dp[i] = min{dp[j]+1}  | isPalin[i][j]=True

答案是F[N]-1 最少划分几次    F[N]：表示以N为结尾有最少多少回文串。

时间复杂度 0(n^2)   空间复杂度 0(n^2)

 1 public class Solution {
 2     /**
 3      * @param s: A string
 4      * @return: An integer
 5      */
 6     public int minCut(String ss) {
 7         // write your code here
 8         char[] s = ss.toCharArray();
 9         int n = s.length;
10         if(n==0){
11             return 0;
12         }
13         boolean[][]  isPalin = new boolean[n][n];
14         for(int i=0; i<n; i++){
15             for(int j=0; j<n; j++){
16                 isPalin[i][j] = false;
17             }
18         }
19         int i, j, t;
20         // 判断i到j是否为回文串
21         for(t=0; t<n; t++){
22             // old-length
23             i=j=t;
24             while(i>=0 && j<n && s[i]==s[j]){
25                 isPalin[i][j] = true;
26                 i--;
27                 j++;
28             }
29             
30             // even length
31             i = t;
32             j = t+1;
33             while(i>=0 && j<n && s[i]==s[j]){
34                 isPalin[i][j] = true;
35                 i--;
36                 j++;
37             }
38         }
39         
40         int[] dp = new int[n+1];
41         dp[0]=0;
42         for(i=1; i<=n; i++){
43             dp[i] = Integer.MAX_VALUE;
44             for(j=0; j<i; j++){
45                 if(isPalin[j][i-1]){
46                     dp[i] = Math.min(dp[j]+1, dp[i]);
47                 }
48             }
49         }
50         
51         // dp[i] = min j=0..i-1 {f[j]+1 | isPalin[j][i-1] = True}
52         
53         return dp[n]-1;
54     }
55 }

题目3：LintCode 437 Copy Books

K个抄写员，可以抄写连续的若干本(每个抄写员碎度都一样每一份一页)

问最少需要多少时间可以抄写完

抄写员抄写第i本到第j本需要时间 : A[i]+A[i+1]+...+A[j]

找一种划分方式，不超过k段，使得每段所有的数字之和的最大值最小

最后一步：A[j]+..+A[N-1]

需要知道钱k-1个人最少需要多少时间抄写完前j本书（0-j-1本书）

f[k][i]:为k个抄写员最少需要多少时间抄完前i本书  （如果这边加k就表示抄写员的个数为任意多个，用k来记录状态）

f[k][i] = min {max{f[k-1][j], A[j]+A[j+1]+...+A[i-1]}}

         j=0,...,j

初始条件：

• f[0][0]=0,   
• f[0][1]=f[0][2]=...=f[0][N]=+无穷 代表不能抄,去最小值
• f[k][0]=0;

 1 public class Solution {
 2     /**
 3      * @param pages: an array of integers
 4      * @param k: An integer
 5      * @return: an integer
 6      */
 7     public int copyBooks(int[] A, int K) {
 8         // write your code here
 9         int n = A.length;
10         if(n==0){
11             return 0;
12         }
13         if(K > n){
14             K = n;
15         }
16         
17         int[][] dp = new int[K+1][n+1];
18         int i, j, k;
19         
20         dp[0][0] = 0;
21         for(j=1; j<=n; j++){
22             dp[0][j] = Integer.MAX_VALUE;
23         }
24         
25         int sum = 0;
26         for(k=1; k<=K; k++){
27             dp[k][0] = 0;
28             for(i=1; i<=n; i++){
29                 sum = 0;
30                 dp[k][i] = Integer.MAX_VALUE;
31                 //import j 是从j到i-1
32                 for(j=i; j>=0; j--){
33                     dp[k][i] = Math.min(dp[k][i], Math.max(dp[k-1][j], sum));
34                     if(j > 0){
35                         sum += A[j-1];
36                     }
37                 }
38             }
39             // f[k][j] = min j=0..i {max{f[k-1][j], A[j]+...+A[i-1]}}
40         }
41         
42         return dp[K][n];
43     }
44 }