挑战程序竞赛系列（3）：2.3需要思考的动规

用户1147447

发布于 2019-05-26 09:44:14

4220

发布于 2019-05-26 09:44:14

文章被收录于专栏：机器学习入门机器学习入门

2.3 需稍加思考的动态规划

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 1065: Wooden Sticks

n根木材长l_i重w_i，前一根木材大于后一根的话要浪费一分钟准备机器，求最省方案？

思路：

如果只有长度为li的情况下，答案永远都是1。所以关键问题在于两个维度，不能够同时满足L和W分别递增。所以我们能想到的是，尽量去满足一个维度递增，所以对长度L进行排序。
每个子序列总能满足长度L和重量W都递增。

求这样的子序列最小值x，该问题等价于按L递增排序后stick按W最长下降子序列的长度h。

这点很关键，现在我们假设木块已经按照长度L递增，现在只关注W的相对顺序。

x = 1，那么这意味着，w均为递增才能符合这种情况。如果出现一个递减，那么必然不符合。
x = 2，想象一下，符合递增的放在一个“空位”上，而遇到第一个递减元素，就放在另外一个“空位”上，当出现第三个递减时，不管放在哪两个空位上，也都不符合。

所以我们猜测，x = h，h为L递增后stick按W最长下降子序列的长度。

证明：

假设存在　x＜h，那么安排x个“容器”，我们知道在该序列中存在h个连续递减的子序列，它们不可能放在一个容器内，所以尽可能的放在每个容器中，但很不幸，由于鸽笼原理，必然会有一对递减序列放在同一个容器中，与命题矛盾。所以必然有x≥hx\ge h。代码如下：

public class SolutionDay05_P1065 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int i = 0; i < T; i++){
            int n = in.nextInt();
            int[] l = new int[n];
            int[] w = new int[n];
            for (int j = 0; j< n; j++){
                l[j] = in.nextInt(); 
                w[j] = in.nextInt();
            }
            System.out.println(solve(l, w));
        }
        in.close();
    }

    public static int solve(int[] l, int[] w){
        int n = l.length;
        Pair[] pairs = new Pair[n];
        for (int i = 0; i < n; i++){
            pairs[i] = new Pair(l[i],w[i]);
        }

        Arrays.sort(pairs, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.start != o2.start ? o1.start-o2.start : o1.end - o2.end;
            }
        });

        int[] dp = new int[n];
        int len = 0;
        for (int i = 0; i < n; i++){
            int index = Arrays.binarySearch(dp, 0,len,-pairs[i].end);
            if (index < 0)
                index = -(index + 1);
            dp[index] = -pairs[i].end;
            if (index == len)
                len ++;
        }

        return len;
    }
}

class Pair{
    int start;
    int end;
    Pair(int start, int end){
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "["+start+","+end+"]";
    }
}

POJ 1631: Bridging Signals

新来的实习生把路由线路搞得一团糟！如图，原本左右端口应当按顺序连接。现在只有切除部分线路，使得任何线路都不相交。希望你写一个程序计算最后剩下多少线路？

好吧，观察一下，就是求最长递增子序列。代码如下：

public class SolutionDay05_P1631 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            int p = in.nextInt();
            int[] map = new int[p];
            for (int j = 0; j < p; j++) {
                map[j] = in.nextInt();
            }
            System.out.println(solve(map));
        }

        in.close();
    }

    public static int solve(int[] map) {
        int[] dp = new int[map.length];
        int len = 0;
        for (int i = 0; i < map.length; i++) {
            int index = Arrays.binarySearch(dp, 0, len, map[i]);
            if (index < 0) {
                index = -(index + 1);
            }
            dp[index] = map[i];
            if (index == len) {
                len++;
            }
        }

        return len;
    }

}

POJ 3666: Making the Grade

农夫约翰想修一条尽量平缓的路，路的每一段海拔是A_i，修理后是B_i，花费|A_i – B_i|，求最小花费。

求构成上升或下降序列的最小花费。

dp[i][j]：表示前i-1个序列递增且第i-1个序列为第j-1小的最小花费。即：第i个序列为第j小。

递推式：
dp[i][j] = Math.min(dp[i-1][k]) + |A[i]-B[j]|
数组B为A的单调递增数组

举个例子：
A = [1, 3, 2]
B = [1, 2, 3]

所以有：
dp[0][0] = 0;  可以想象当前数组被修改成：  1
dp[0][1] = 1;  可以想象当前数组被修改成：  2
dp[0][2] = 2;  可以想象当前数组被修改成：  3

dp[1][0] = 2;  可以想象当前数组被修改成：  1 1
dp[1][1] = 1;  可以想象当前数组被修改成：  1 2
dp[1][2] = 0;  可以想象当前数组被修改成：  1 3

dp[2][0] = 3;  可以想象当前数组被修改成：  1 1 1
dp[2][1] = 1;  可以想象当前数组被修改成：  1 2 2
dp[2][2] = 1;  可以想象当前数组被修改成：  1 3 3

问题求解思路，证明过程，仅供自己参考：
|A[0]-B[0]| + |A[1]-B[1]| + ... + |A[i-1]-B[i-1]| + |A[i]-B[i]| = MIN_COST;

数学归纳：
假设我们已经找到了|A[0]-B[0]| + |A[1]-B[1]| + ... + |A[i-1]-B[i-1]|的MIN_COST，那么前`i-1`个元素必然已经递增or递减。

一个想法：求min(A[i]-B[i]),但B[i]的值哪来？
答：直接从A的升序排列得到。这对我来说有点难以证明，一个直观的想法是，当我们在填坑或者挖坑时，我们有意识的会比较周围的两个元素，与之对齐。所以B[i]的取值实际上就是A[i]中的任何一个。如果超过某个A[i],必然不会有更小的|A[i]-B[j]|.

这就意味着，我们得尝试各种不同的B[j],而上述递推式就变成了：
min(A[i]-B[j])

这也就说明dp需要多保存一维的状态dp[i][j],i表示阶段，而j是状态。答案出来了，有了多个状态，那就意味着dp[i-1][j]也是多状态的，因为我们并不确定最后一个元素到底应该选择谁，所以我们都得保存下来。但我们确定了一件事，一旦最后一个元素被状态选定，那就意味着之前的i-1个序列一定是单调递增的。

因为我们B[j]的选择是有顺序的，dp[i][j]选的一定是第i-1个元素为第j-1大的，所以为了取得最小的|A[i]-B[j]|,一定选择第j大的元素。证毕。

代码如下：

public class SolutionDay05_P3666 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        System.out.println(solve(A));
        in.close();
    }

    public static int solve(int[] A) {
        int n = A.length;
        int[][] dp = new int[n][n];

        int[] B = new int[n];
        System.arraycopy(A, 0, B, 0, n);

        // 非严格递增
        Arrays.sort(B);

        for (int j = 0; j < n; ++j) {
            dp[0][j] = Math.abs(A[0] - B[j]);
        }
        for (int i = 1; i < n; ++i) {
            int pre_min_cost = dp[i - 1][0];
            for (int j = 0; j < n; ++j) {
                pre_min_cost = Math.min(pre_min_cost, dp[i - 1][j]);
                dp[i][j] = pre_min_cost + Math.abs(A[i] - B[j]);
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, dp[n - 1][i]);
        }
        return min;
    }
}

更新只跟i和i-1相关，可以使用滚动数组，代码如下：

public static int solve(int[] A) {
        int n = A.length;
        int[][] dp = new int[2][n];

        int[] B = new int[n];
        System.arraycopy(A, 0, B, 0, n);

        // 非严格递增
        Arrays.sort(B);

        for (int j = 0; j < n; ++j) {
            dp[0][j] = Math.abs(A[0] - B[j]);
        }
        for (int i = 1; i < n; ++i) {

            int cur = i % 2;
            int pre = (i - 1) % 2;

            int pre_min_cost = dp[pre][0];
            for (int j = 0; j < n; ++j) {
                pre_min_cost = Math.min(pre_min_cost, dp[pre][j]);
                dp[cur][j] = pre_min_cost + Math.abs(A[i] - B[j]);
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, dp[(n - 1) % 2][i]);
        }
        return min;
    }

POJ 2392: Space Elevator

通天塔：奶牛们想用c_i个高h_i的积木造通天塔，每种积木不能高过a_i，求塔的最大高度。

思路：

首先，a_i必须从小到大排序，否则压根就堆不上去，想象一下即可。所以该问题就转成了01背包问题，在指定的高度内，选择最多的价值。

测试用例：

3
7 40 3
5 23 8
2 52 6

排序后：
5 23 8
7 40 3
2 52 6

我们看：
5 23 8
意思就是背包总重23，物品（价值，重量）
(5,5) // 选 or 不选
(5,5) // 选 or 不选
(5,5) // ...
(5,5)
(5,5)
(5,5)
(5,5) // ...
(5,5) // 选 or 不选

dp[j] ： 表示指定高度下，积木所能堆积的最大高度。

递推式：
dp[j] = Math.max(dp[j],dp[j-p[i].h] + p[i].h);

代码如下：

private static class Pair {
        int h;
        int a;
        int c;

        Pair(int h, int a, int c) {
            this.h = h;
            this.a = a;
            this.c = c;
        }
    }

    public static int solve(int[] H, int[] A, int[] C) {
        int n = H.length;
        Pair[] p = new Pair[n];
        for (int i = 0; i < n; i++) {
            p[i] = new Pair(H[i], A[i], C[i]);
        }

        Arrays.sort(p, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.a - o2.a;
            }
        });

        int[] dp = new int[40000 + 16];

        for (int i = 0; i < n; i++){
            for (int k = p[i].c; k >= 1; k--){
                for (int j = p[i].a; j >= p[i].h; j--){
                    dp[j] = Math.max(dp[j], dp[j-p[i].h] + p[i].h);
                }
            }
        }

        int max = 0;
        for (int j = p[n-1].a; j >= 0; j--){
            max = Math.max(max, dp[j]);
        }
        return max;
    }

很可惜这种时间复杂度为O(n⋅c⋅a)O(n\cdot c\cdot a). 它的时间复杂度还可以进一步降低为O(NV)O(NV).达到该目标需要了解如何利用单调性优化动态规划。

用单调性优化动态规划

一份新的内容，参考了JOSI2009集训队的论文，下载【此文】。先来看到题：

一个含有n项的数列(n<=2000000)，求出每一项前面的第m个数到它这个区间内的最小值。

一种朴素的做法，每当遍历到第i个元素后，便遍历前m个元素，取其中最小值即可。如果用数组记录下来，我们可以表示为如下表达式：

f(i+1)=minj=i−m+1i(aj)

f(i+1) = \min_{j = i - m +1}^{i}(aj)

Example 1:
a : 1 2 3 4 5 6     m = 2
f : 0 1 1 2 3 4

Example 2:
a : 7 8 1 4 3 2     m = 2
f : 0 7 7 1 1 3

单调队列有点类似滑动窗口，分别维护了front指针和rear指针，front用来输出答案，rear用于维护队列元素的单调性。

可以优化的地方也很明显，因为它类似于滑动窗口，之前是无状态记录，而现在我们可以用某个容器来记录之前的状态，这样当遍历下一个元素时，窗口重复的地方就不需要再扫描。

为了满足答案的正确性，我们定义了该记录状态的容器为满足单调性的队列。来看看这递推表达式：

f(i+1)=minj=i−m+1i(aj)

f(i+1) = \min_{j = i - m +1}^{i}(aj)

可以想象，当我们遍历到第i+1个元素时，一定扫描过前i个元素，而答案只需要前m个元素的最小值。显然，答案与前m个元素顺序无关，而这种顺序无关便是我们利用的地方，既然顺序无关，我们就给它排个序，一旦排序，我们便能有方向性的记录状态，其次，输出就按照顺序一个个从队列取即可。此时，队列只需要满足两个性质：

队尾加入的元素符合单调递增
队首不断删除不在前i-m+1个元素的候选答案（以第i+1个元素为视角）

所以代码如下：

private static void solve(int[] a, int m){
        int n = a.length;
        int[] q = new int[n];
        int[] f = new int[n];
        f[0] = 0;
        int front = 0, rear = 0;
        for(int i = 0; i < n-1; i++){
            //队列中最小元素的坐标小于i-m+1，直接删除，不再需要
            while (front <= rear && (q[front] < (i - m+1))) front++; //删除
            while (front <= rear && a[i] <= a[q[rear]]) rear--; //加入  
            // a[i] > a[q[rear]] 加入的元素为单调递增， 从队尾加入单调递增的元素
            q[++rear] = i;
            // 取的元素一定是头
            f[i+1] = a[q[front]];
        }

        for (int i = 0; i < n; i++){
            System.out.println(f[i]);
        }
    }

总结

对于这样一类动态规划问题，我们可以运用单调队列来解决：

f(x)=optx−1i=boundx

f(x) = opt_{i = boundx}^{x-1}(consti)

其中boundx随着x单调不降，而consti则是可以根据i在常数时间内确定的唯一常数。这类问题，一般用单调队列在很优美的时间内解决。

继续看POJ 2392: Space Elevator，我们有递推式：

dp[i][j] = max {dp[i-1][j-k*v[i]]+k*w[i]} (0 <= k <= m[i])

举个简单的例子，当我们选择某个物品i时，假设最大容量为W = 12, w = 3, v = 3，则我们有：

dp[i][j = 12] = max{
d[i-1][12 - 0 * w] + 0 * v = dp[i-1][12] + 0 * v;
d[i-1][12 - 1 * w] + 1 * v = dp[i-1][09] + 1 * v;
d[i-1][12 - 2 * w] + 2 * v = dp[i-1][06] + 2 * v;
d[i-1][12 - 3 * w] + 3 * v = dp[i-1][03] + 3 * v;
d[i-1][12 - 4 * w] + 4 * v = dp[i-1][00] + 4 * v;
}

dp[i][j = 9] = max{
d[i-1][9- 0 * w] + 0 * v = dp[i-1][9] + 0 * v;
d[i-1][9- 1 * w] + 1 * v = dp[i-1][6] + 1 * v;
d[i-1][9- 2 * w] + 2 * v = dp[i-1][3] + 2 * v;
d[i-1][9- 3 * w] + 3 * v = dp[i-1][0] + 3 * v;
}

如果不考虑价值，我们可以发现，求解dp[9]时，有0,3,6的中间状态，而在求解dp[12]时，同样出现了0，3，6的状态，这就意味着我们可以采取一些手段来降低取max的操作。

上述dp[i][j]求解过程，看图：

关注dp的更新过程，如果更新了dp[i-1][0]，那么紧接着就可以更新dp[i-1][3]，而当我们更新dp[i-1][12]时，我们可以利用单调队列来使得更新操作维持在O(W)O(W)内。

所以，dp[i-1][j]，就可以被划分成k = w = 3份，分别进行O(W/k)O(W/k)次的更新。

于是问题得到了转换，现在要确定：

所以有：
dp[i][j = 12] - 4 * v = max{
dp[i-1][12] + 0 * v - 4 * v = dp[i-1][12] - 4 * v;
dp[i-1][09] + 1 * v - 4 * v = dp[i-1][09] - 3 * v;
dp[i-1][06] + 2 * v - 4 * v = dp[i-1][06] - 2 * v;
dp[i-1][03] + 3 * v - 4 * v = dp[i-1][03] - 1 * v;
dp[i-1][00] + 4 * v - 4 * v = dp[i-1][00] - 0 * v;
}

dp[i][j = 9] - 3 * v= max{
dp[i-1][09] + 0 * v - 3 * v = dp[i-1][09] - 3 * v;
dp[i-1][06] + 1 * v - 3 * v = dp[i-1][06] - 2 * v;
dp[i-1][03] + 2 * v - 3 * v = dp[i-1][03] - 1 * v;
dp[i-1][00] + 3 * v - 3 * v = dp[i-1][00] - 0 * v;
}

经过如上变换后，更新公式中的dp[i-1][j-k*w]-k*v就可以看成整体，用单调队列在O(w)的时间内解决，最后更新的答案加上j/w * v 即可。

由此得递推式：
dp[i][mod + x * w] = max{dp[i-1][mod + y * w] - y * v} + x * v;

代码如下：

public class SolutionDay08_P2392 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int K = in.nextInt();
        int[] H = new int[K];
        int[] A = new int[K];
        int[] C = new int[K];

        for (int i = 0; i < K; i++) {
            H[i] = in.nextInt();
            A[i] = in.nextInt();
            C[i] = in.nextInt();
        }
        System.out.println(solve(H, A, C));
        in.close();
    }

    public static int solve(int[] H, int[] A, int[] C) {
        int n = H.length;
        Pair[] p = new Pair[n];
        for (int i = 0; i < n; i++) {
            p[i] = new Pair(H[i], A[i], C[i]);
        }

        Arrays.sort(p, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.a - o2.a;
            }
        });

        int[][] dp = new int[2][40000 + 16];
        Queue[] q = new Queue[40000 + 16];

        int[] pos = { 0, 1 };
        for (int i = 0; i < n; i++) {
            swap(pos);
            int v = p[i].h; // 价值
            int w = p[i].h; // 重量
            int m = p[i].c; // 数量

            int V = p[i].a;

            // 划分成w份
            for (int mod = 0; mod < w; ++mod) {
                int l = 0, r = 0;
                //更新dp[mod],dp[mod+w],dp[mod+2w],dp[mod+3w],...,d[V]
                for (int j = 0; mod + j * w <= V; ++j) {
                    // 维持单调队列的递减特性
                    while (r > l && (dp[pos[1]][mod + j * w] - j * v) > q[r - 1].first) {
                        // 将前面小的元素都挤出去
                        r--;
                    }
                    // 入队
                    q[r++] = new Queue(dp[pos[1]][mod + j * w] - j * v, j);
                    if (r - l > 0 && j - q[l].second > m) {
                        // 队列不为空，最优解对应的缺口无法填满，出队
                        l++;
                    }
                    dp[pos[0]][mod + j * w] = q[l].first + j * v;
                }
            }
        }

        int max = 0;
        for (int i = 0; i < p[n - 1].a + 1; i++) {
            max = Math.max(max, dp[pos[0]][i]);
        }

        return max;
    }

    private static class Pair {
        int h;
        int a;
        int c;

        Pair(int h, int a, int c) {
            this.h = h;
            this.a = a;
            this.c = c;
        }
    }

    private static void swap(int[] pos) {
        int tmp = pos[0];
        pos[0] = pos[1];
        pos[1] = tmp;
    }

    private static class Queue {
        int first;
        int second;

        Queue(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}

POJ 2184: Cow Exhibition

奶牛CJ：有N头奶牛想参加CJ，每头奶牛的智商分别为S_i，情商为F_i。欲挑出一群奶牛使得S之和与F之和都不为负数，且SF之和最大，求此最大值。

一道特殊的01背包问题，针对负和的情况，我们进行数组扩充。简单说明下思路：

首先，s和f存在相互依赖关系，所以我们的目标是生成所有可能的由Si组成的和，而我们又知道，可能在生成过程中，遇到相同和，却由不同的Si组成，因此，在这种情况下我们选取最大的TF，所以递推式如下：

dp[j] = Math.max(dp[j],dp[j-S[i]] + F[i]);

那么不管TS是正的也好负的也好，我们需要算出TS的和在0,sum+1这个范围内的所有可能组合。而至于为什么要初始化dp数组为-INF，是因为不是所有的在0,sum+1的j是合法的。代码如下：

public class SolutionDay09_P2184 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] S = new int[N];
        int[] F = new int[N];
        for (int i = 0; i < N; i++){
            S[i] = in.nextInt();
            F[i] = in.nextInt();
        }
        System.out.println(solve(S, F));

        in.close();
    }

    //注意INF不能取最小值，尽量小即可，否则会溢出！
    static int INF = 1<<30;
    private static int solve(int[] S, int[] F){
        int n = S.length;
        int sum = 0;
        for (int i = 0; i < n; i++){
            sum += S[i] >= 0 ? S[i] : -S[i];
        }

        int[] dp = new int[sum * 2 + 1];
        //存在不合法的TS
        Arrays.fill(dp, -INF);

        int center = sum;
        int range = sum * 2;
        dp[center] = 0;

        for (int i = 0; i < n; i++){
            if (S[i] >= 0){
                //所有可能的正和下最大的TF
                for (int j = range; j >= S[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j-S[i]] + F[i]);
                }
            }else{
                //正和 - S[i] > 0的值也是合法的
                for (int j = 0; j <= range + S[i]; j++){
                    dp[j] = Math.max(dp[j], dp[j-S[i]] + F[i]);
                }
            }
        }

        int res = -INF;
        for (int i = center; i <= range; i++){
            if (dp[i] >= 0){
                res = Math.max(res, dp[i] + i - center);
            }
        }
        return res;
    }
}

这五题做的心累，动态规划暂告一段落了。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年05月09日，如有侵权请联系 cloudcommunity@tencent.com 删除

容器

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

容器

编程算法

登录后参与评论

0 条评论

热度