@[toc]

D4 划分型动态规划

常见类型：

给定长度为N的序列或字符串，要求划分成若干段
- 段数不限，或指定K段
- 每一段满足一定的性质
做法
- 类似于序列型动态规划，但是通常要加上段数信息
- 一般用f[i][j]记录前i个元素（元素0~i-1）分成 j 段的性质，如最小代价

Perfect Squares

题意：

给定一个正整数n，问最少可以将n分成n个完全平方数（1，4，9，…）之和

样例

Input
13
Output
2 (13 = 4 + 9)

分析

确定状态：

最后一步：关注最优策略中最后一个完全平方数
最优策略中n-j^2 也一定被划分成最少完全平方数之和
需要知道n-j^2 最少被分成几个完全平方数之和
原来是求n最少被分成几个完全平方数之和
子问题：设f[i] 表示i 最少被分为几个完全平方数之和

转移方程： f[i] = min(i<=j*j<i){f[i-j^2]+1} 时间复杂度为：n√n

i 最少被分成几个完全平方数之和
最后一个完全平方数是 j^2
i-j^2 最少被分成几个完全平方数之和

初始条件： f[0]=0

public int numSquares(int n){
    int[] f = new int[n+1];
    f[0]=0;
    int i,j;
    for(i=1;i<=n;i++){
        f[i] = Integer.MAX_VALUE;
        for(j=1;j*j<=i;j++){
            f[i] = Math.min(f[i],f[i-j*j]+1);
        }
    }
    return f[n];
}

Palindrome Partitioning II

Problem：

给定一个字符串S[n…N-1]，要求将这个字符串划分成若干段，每一段都是一个回文串，求最少划分几次

Example

Input
"aab"
Output
1  -> "aa,b"

分析

子问题： 设S前i个字符S[0...i-1] 最少可以划分成f[i] 个回文串

转移方程： 设f[i]为S前i个字符S[0…i-1]最少可以划分成几个回文串

f[i] = min(j=0,...,j=i-1){f[j]+1|S[j...i-1]是回文串}

S前i个字符串最少可以划分成几个回文串
S前j个字符串最少可以划分成几个回文串
最后一段回文串

public boolean[][] calcPalin(char[] s){
    int n = s.length;
    boolean[][] f = new boolean[n][n];
    int i,j,c;
    for(i=0;i<n;i++){//initialize
        for(j=0;j<n;j++){
            f[i][j] = false;
        }
    }
    //odd length: center character
    for(c=0;c<n;c++){
        i=j=c;
        //extend to both direction
        while(i>=&&j<n&&s[i]==s[j]){
            f[i][j] = true;
            --i;
            ++j;
        }
    }
    //even length center line
    for(c=0;c<n-1;c++){
        i=c;
        j=c+1;
        while(i>=0&&j<n&&s[i]==s[j]){
            f[i][j]=true;
            i--;
            j++;
        }
    }
    return f;
}
public int minCut(String ss){
    char[] s =  ss.toCharArray();
    int n = s.length;
    if(n==0)return 0;
    boolean[][] isPalin = calcPalin(s);//思考为什么这样求回文串
    int i,j;
    int[] f = new int[n+1];
    f[0] = 0;
    for(i=1;i<=n;i++){
        f[i]=Integer.MAX_VALUE;
        for(j=0;j<i;j++){
            if(isPalin[j][i-1]){
                f[i] = Math.min(f[i],f[j+1]);
            }
        }
    }
    return f[n]-1;
}

Copy Books

Problem:

给定 n 本书, 第 i 本书的页数为 pages[i]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages[0], pages[1], pages[2], 但是不可以只复印 pages[0], pages[2], pages[3] 而不复印 pages[1].

所有人复印的速度是一样的, 复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?

求返回完成复印任务最少需要的分钟数.（书籍页数总和小于等于2147483647）

样例 1:

1
2
3

输入: pages = [3, 2, 4], k = 2
输出: 5
解释: 第一个人复印前两本书, 耗时 5 分钟. 第二个人复印第三本书, 耗时 4 分钟.

思路：

子问题： 设f[k][i]为前k个抄写员最少需要多少时间抄完前i本书

转移方程： f[k][i] = min(j=0,...i){max{f[k-1][j],A[j]+...+A[i-1]}}

k个抄写员最少需要多少时间抄完前i本书
k-1 个抄写员最少需要多少时间抄完前j本书
第k个抄写员抄完第 j 至第 i-1 本书的时间

初始条件：

0个抄写员只能抄0本书

f[0][0]=0,f[0][1]f[0][2]=...=f[0][N]=+oo
k个抄写员（k>0）需要0时间抄0本书

f[k][0] = 0 (k>0)

public int copyBooks(int[] A, int K) {
        int n = A.length;
        if (n == 0)
            return 0;
        if (K > n) {
            K = n;
        }
        int[][] f = new int[K + 1][n + 1];
        int i, j, k;
        f[0][0] = 0;
        for (i = 1; i <= n; i++) {
            f[0][i] = Integer.MAX_VALUE;
        }
        for (k = 1; k <= K; k++) {
            f[k][0] = 0;
            for (i = 1; i <= n; i++) {
                f[k][i] = Integer.MAX_VALUE;
                // A[j]+...+A[i-1]
                int sum = 0;
                for (j = i; j >= 0; j--) {
                    // sum=A[j]+...+A[j-1]
                    // f[k][i]=minj=0,...,i{max{f[k-1][j],A[j]+...+A[i-1]}}
                    f[k][i] = Math.min(f[k][i], Math.max(f[k - 1][j], sum));
                    if (j > 0) {
                        sum += A[j - 1];
                    }
                }
            }
        }
        return f[K][n];
    }

划分型动态规划小结

要求将一个序列或字符串划分成若干满足要求的片段
解决方法：最后一步 -> 最后一段
枚举最后一段的起点

如果题目不指定段数，用 f[i] 表示前i个元素分段后的可行性/最值，可行性，方式数：Perfect Squares、Palindrome Partition II
如果题目指定段数，用f[i][j]表示前i个元素分成j段后的可行性/最值，可行性，方式数：Copy Books