博客

Java数据结构与算法：动态规划

  • Post author:
  • Post category:java


牛客网来的朋友可以直接跳到第 3 题，这里的分析过程和我之前评论不一样，我改进了很多当初描述不到位的地方。

本篇文章通过几道题目希望让读者对简单的动态规划问题有一个清晰的解题思路，对于复杂动态规划问题，欢迎提出来和我一起探讨呀，哈哈。

0. 结论放在前面

在理解了这几道题目的思想之后，相信你也会有这样的认识：

  1. 动态规划的问题，首先要能找到

    递推公式

    ，也就是大问题的最优解是几个小问题最优解的组合。
  2. 要能找到基本的初始条件，也就是

    边界条件

    。
  3. 通过

    填表格

    能很快理解递推的关系，方便书写程序。
  4. 最好先写出

    伪代码

    ，这样方便我们看出代码的逻辑层次，后面写代码会简单很多。

1. 计算二项式系数

在统计数学中，有一个排列组合的公式：


when n > k > 0, there is C(n, k) = C(n-1, k-1) + C(n-1, k)

那么如果给我们任意正整数 n 和 k 值（0 <= k <= n），我们如何编程计算 C(n, k) ？

下面我们用动态规划的思路来解决这个问题。

首先我们有了上面的

递推公式

。

其次，根据数学知识，我们可以知道

边界情况

：


C(n, n) = C(n, 0) = 1, C(0, 0) = 1

动态规划的递推公式是从上向下分析问题，现在我们需要从下向上

填表格

，表格中的值为

C(i, j)

：

i \ j 0 1 2 … k-1 k
0 1
1 1 1
2 1 … 1
… … …
k – 1 1 … 1
k 1 … 1
… … …
n – 1 1 … C(n-1, k-1) C(n-1, k)
n 1 … C(n, k)

我们可以用伪代码书写思路： 

k = 0 -> return 1;
k = n -> return 1;
new long a[n][k+1]

// 首先填充第 0 列元素：
for i from 0 to n
    a[i][0] = 1;

// 然后处理 i = j 的情况：
for i from 0 to k
    a[i][i] = 0;

//最后利用公式进行迭代：
for i from 1 to n
    i <= k -> for j from 1 to i - 1
                a[i][j] = a[i - 1][j] + a[i - 1][j - 1]
    i > k -> for j from 1 to k
                a[i][j] = a[i - 1][j] + a[i - 1][j - 1]

我们这里采用了二维数组来表示表格，有很多空间被浪费掉了，我们发现只要知道的第 i 行的数据就可以用公式推算出第 i – 1 行的数据，所以实际上，我们可以用一个一维数组来解决递推，修改后的伪代码如下： 

k = 0 -> return 1;
k = n -> return 1;
new long a[k+1];

// 首先，填充第 0 列：
a[0] = 1;

// i = j 的情况在递推中处理：
i: 1 -> n
    如果 i <= k =>   a[i] = 1;
                    j: i - 1 -> 1 // 可以思考下为什么不是 1 -> i - 1
                        a[j] += a[j - 1];
    如果 i > k =>    j: k -> 1     // 可以思考下为什么不是 1 -> k
                        a[j] += a[j - 1];

伪代码写完之后，代码写起来就简单了： 

public static long binomial(int n, int k) {
    assert n >= k && k >= 0;
    if (k == 0 || k == n) {
        return 1;
    }

    long[] a = new long[k + 1];
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i <= k) {
            a[i] = 1;
            for (int j = i - 1; j >= 1; j--) {
                a[j] += a[j - 1];
            }
        } else {
            for (int j = k; j >= 1; j--) {
                a[j] += a[j - 1];
            }
        }
    }
    return a[k];
}

public static void startTest() throws IOException {
    int n = 8;
    for (int k = 0; k <= n; k++) {
        System.out.print(binomial(n, k));
        if (k != n) {
            System.out.print(", ");
        }
    }
}
// 1, 8, 28, 56, 70, 56, 28, 8, 1

2. 01 背包问题

有编号为 a，b，c，d，e 的5件宝物在山洞，它们的重量分别是2、2、6、5、4，它们的价值分别是6、3、5、4、6，现在给你一个承重为 10 的背包。请问怎么装背包，才能带走最多的财富?

首先我们给宝物编号 0、1、2、3、4，然后定义重量数组

w = {2, 2, 6, 5, 4}

，宝物价值数组

p = {6, 3, 5, 4, 6}

。

f(i, j)

表示承重为 j 的背包装走标号为i、i+1、…4 的宝物的最优解。

分析：

  • 首先，我们从宝物 a 开始，如果我们装宝物 0，那么背包的剩下容量就是 c – w[0]，而且我们得到了财富 p[0]，如果我们选择放弃宝物 0，那么背包的剩下容量还是 c，没有得到财富。所以背包问题

    f(0, c)

    的最优解就是

    f(1, c)

    和

    f(1, c - w[0]) + p[0]

    的最大值。

因此我们可以得到

递推公式

： 

f(i, j) = max{ f(i+1, j), f(i+1, j-w[i])+p[i] }   when j >= w[i]
f(i, j) = f(i+1, j)   when j < w[i]

我们看看

边界条件

（只有 n 个宝物时，最后一件宝物编号是 n – 1）： 

f(n-1, j) = 0   when j < w[n-1] // 最后一件宝物重量超过背包的容量
f(n-1, j) = p[n-1]   when j >= w[n-1] // 没有超过

在从上往下分析完问题后，我们根据初始条件，可以从下往上

填表格

，表格中的数据为 f(i, j)，即承重为 j 的背包装走标号为i、i+1、…4 的宝物的最优解

p[i] w[i] i \ j 0 1 2 3 4 5 6 7 8 9 10
6 4 4 0 0 0 0 6 6 6 6 6 6 6
4 5 3 10
5 6 2
3 2 1
6 2 0

比如，计算 f(3,9) 时，我们就要比较

f(4, 9)

和

f(4, 9 - w[3]) + p[3]

的最大值，查上一行知，

f(4, 9) = 6

，而

f(4, 9 - w[3]) + p[3]

=

f(4, 9 - 5) + 4

=

6 + 4 = 10

，所以

f(4, 9) = 10

。

伪代码如下，这里我们借鉴上一题的经验，因为可以用第 i 行推导第 i – 1 行，所以可以用一维数组来计算： 

int[] a = new int[11];

// 首先，初始化第 4 行
j: 0 -> 10
    如果 j < w[4] => a[j] = 0;
    否则          => a[j] = p[4]  

// 然后，用递推公式推导下一行
i: 3 -> 0
    j: 10 -> 0
        如果 j >= w[i]    => int tmp = a[j - w[i]] + p[i];
                            如果 tmp > c[y] => c[y] = tmp; // 取最大值

return a[10];

伪代码写完后，实际代码就很好写了： 

// weight[0] 和 price[0] 无意义
// 宝物对应的索引为 1-N
public static int packTreasure(int[] weight, int[] price,
        int capacity, int N) {
    int[] c = new int[capacity + 1];
    c[0] = 0;
    for (int y = 1; y <= capacity; y++) {
        c[y] = (y < weight[N]) ? 0 : price[N];
    }
    for (int i = N - 1; i >= 1; i--) {
        for (int y = capacity; y >= 1; y--) {
            if (y >= weight[i]) {
                int tmp = c[y - weight[i]] + price[i];
                if (tmp > c[y]) {
                    c[y] = tmp;
                }
            }
        }
    }
    return c[capacity];
}

public static void startTest() throws IOException {
    int N = 5;
    int[] weight = {0, 2, 2, 6, 5, 4};
    int[] price = {0, 6, 3, 5, 4, 6};
    int capacity = 10;
    System.out.println(packTreasure(weight, price, capacity, N));
}
// 15

3. 钱币组合

这是牛客网上的一道题，算是 01 背包问题的变种。

给你六种面额的纸币 {1、5、10、20、50、100元}，假设每种币值的数量都足够多，编写程序求组成 N 元（N为 0-10000 的非负整数）的不同组合的个数。

首先，我们给纸币面额编号 0、1、2、3、4、5，面额数组

p = {1, 5, 10, 20, 50, 100}

，定义

f(i, j)

表示用面额编号为 0、1、…i 的纸币面额，组成 j 元的组合个数。

分析：

  • 首先，我们从最大面额 100 开始，1000 元的所有组合中，如果我们不使用面额 100（p[5]），那么问题就变成了用剩下的面额来组合 1000 元，即

    f(4, 1000)

    ，如果我们使用面额 100（p[5]），那么我们至少使用了一张，问题可以简化为用面额数组表示剩下的 900 元，即

    f(5, 900)

    。
  • 所以

    f(5, 1000)

    的组合个数为

    f(4, 1000)

    与

    f(5, 1000 - p[5])

    的和。

因此我们可以得到

递推公式

： 

f(i, j) =
            f(i-1, j)                   j 小于面额 p[i] 时
            f(i-1, j) + f(i, j - p[i])  大于时
            f(i-1, j) + 1               等于时


边界条件

： 

f(1, j) = 1, 当 y 大于 0 时 // 任何大于 0 的 j 元钱，都可以用 j 张 1 元来组合
j = 0 时 return 0 // 组成 0 元的组合是不存在的，所以输入 0 元时，我们应该输出 0

在从上往下分析完问题后，我们根据初始条件，可以从下往上

填表格

，表格中的数据为 f(i, j)，即用面额编号为 0、1、…i 的纸币面额，组成 j 元的组合个数。

p[i] i \ j 0 1 2 3 4 5 6 7 8 9 10
1 0 1 1 1 1 1 1 1 1 1 1
5 1 2 3
10 2
20 3
50 4
100 5

比如，计算

f(1, 5)

时，根据递推公式，p[1] = 5，所以我们要计算

f(0, 5) + 1

= 2。计算

f(1, 10)

时，我们要计算

f(0, 10) + f(1, 10 - p[1])

，由左边和上一行的数据知，

f(1, 10 - p[1])

=

f(1, 10 - 5)

=

f(1, 5)

= 2，所以

f(1, 10) = 1 + 2 = 3

。

伪代码如下，因为可以用上一行和本行前几列的数据，所以我们用一维数组计算，注意因为要用到本行前几列的数据，所有计算顺序是从左往右。 

如果 N == 0 => return 0;

int[] p = {1, 5, 10, 20, 50, 100};
int[] a = new int[N + 1];

// 首先，初始化第 0 行数据
j: 1 -> N
    a[j] = 1;

i: 1 -> 5
    j: 1 -> N
        如果 j == p[i] => a[j] += 1;
        如果 j > p[i] => a[j] += a[j - p[i]];

return a[N];

经过观察，我们发现递推中我们没有使用 a[0]，而伪代码的递推关系在计算时（尽管不符合现实意义，0 元钱的组合个数不应该为 1）可以简化为： 

a[0] = 1;
i: 1 -> 5
    j: 1 -> N
        如果 j >= p[i] => a[j] += a[j - p[i]];

简化后的源代码如下： 

public long numOfCombine(int N) {
    if (N < 0) throw new IllegalArgumentException();
    if (N == 0) return 0;

    int[] p = {1, 5, 10, 20, 50, 100};
    long[] a = new long[N + 1];

    for (int j = 0; j <= N; j++){
        a[j] = 1;
    }

    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= N; j++) {
            if (j >= p[i]) {
                a[j] += a[j - p[i]];
            }
        }
    }

    return a[N];
}

4. 连续子数组的最大和

本题是《剑指Offer第二版》第 42 题，之所以放到这里，是因为它很好地说明了动态规划的分析思路：用子问题的最优解来解决父问题的最优解。

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。

记输入的整型数组为 a，数组长度为 N。

  1. 首先，大的问题是求所有子数组的和的最大值。我们发现可以对所有子数组进行分类，分类标准是数组最后一个元素的索引，那么可以得到 N 个子数组：所有以索引 i 为最后一个元素索引的子数组（0 <= i <= N – 1）。

    比如数组 {1, -2, 3, -4} 的以索引 2 为最后一个元素索引的子数组包括 {1, -2, 3}，{-2, 3}，{3}。

  2. 对于每一个小的子数组集合，定义

    f(i)

    为该集合中的所有的子数组和的最大值。比如刚刚的例子中三个子数组的元素和分别为 2、1、3，所以 f(2) 就等于 3 。

  3. 那么我们要求的大问题，就可以转化为比较所有小问题的最优解，得到其中的最大值，也就是

    max{f(0), f(1),...f(N - 1)}

    。

我们可以发现 f(i) 的

递推公式

： 

f(i) =
        f(i - 1) + a[i] //当 f(i - 1) > 0 时
        a[i]            // 当 f(i - 1) <= 0 时


边界条件

：

f(0) = a[0]


填表

：

i 0 1 … i – 1 i … N – 1
f(i) a[0] f(i – 1) f(i) … f(N – 1)

所以我们可以很容易计算任意

f(i)

的值，然后求出他们中的最大值即可。这里的递归很简单，我们不需要构建一维数组，只需要一个临时变量就可以计算任意

f(i)

。

伪代码： 

如果 a.length <= 0 => 抛异常

int max = a[0];
int tmp = a[0];

i: 1 -> a.length - 1
    若 tmp <= 0 => tmp = a[i];
    否则        => tmp += a[i];
    若 tmp > max =? max = tmp;

return max;

Java 代码： 

int findGreatestSumOfSubArray(int[] a) {
    if (a == null || a.length <= 0)
        throw new IllegalArgumentException();

    int max = a[0], tmp = a[0];
    for(int i = 1; i < a.length; i+=) {
        if (tmp <= 1)
            tmp = a[i];
        else
            tmp += a[i];

        if (tmp > max)
            max = tmp;
    }

    return max;
}

5. 01 背包问题进阶：打印数组中和为 SUM 的所有组合

动态规划_打印数组中和为SUM的所有组合1

输入：

7

1

2

4

8

16

32

64

输出：

3

3

6

7


1. 首先，我们可以用动态规划来标记可以添加到组合中的数据

。

定义数组 scores = {-1, 1, 2, 4, 8, 16, 32, 64}，scores[i] 表示编号为 i 的题目的分数（i 在 1 ~ n之间） 。

我们定义 r[i][j] 为总分为 i 时，求标号为 j j+1 … n 的题目能否组合出总分 i。

比如 r[100][7] 表示总分为 100 时，第 7 题能否拼出总分，因为第 7 题的分数为 scores[7] = 64，所以拼不出来，r[100][7] = false，显然 r[64][7] = true。再比如 r[100][6] 表示总分为 100 时，第 6/7 题能否拼出总分，因为第 6 题的分数为 scores[6] = 32，所以拼不出来，但是 r[32][6] = true（第6题分数为32），r[64][6] = true（第 7 题分数为 64），r[96][6] = true（第 6 和 7 题的总分为 96）。

因此我们可以列表：

scores[i] i\j 0 … 32 … 64 … 96 … 100
64 7 true … …
32 6 true true … true …
16 5 … …
8 4 … …
4 3 … …
2 2 … …
1 1 … …

递推公式为： 

当r[i+1][j] == true（组合中无第 i 题） 或者 r[i+1][j-score[i]] == true （组合中有第 i 题）时
    r[i][j] = true

为方便处理第 i 题一定可以组合总分为 score[i] 的情况（只用第 i 题来组合），我们令

r[i+1][0] == true

（仅为计算方便，没有实际意义）。

另一个边界条件是表中第一行的数据，

r[n][score[n]] = true

。

问题不断推导我们就能得出 r[1][100] 的值，也就是原问题是否有解。

伪代码为 

int SUM = 100;
void markResults(int n, int[] scores, boolean[][] r)
{
    // 第一行的数据
    j: 1 -> SUM
        r[n][j] = false;
    r[n][0] = true;
    r[n][scores[n]] = true;

    i: n-1 -> 1
        j: 0 -> SUM
            如果 r[i + 1][j] == true
                |-- r[i][j] = true;
                |-- 如果 j + scores[i] <= SUM
                    |-- r[i][j + scores[i]] = true;
}


2. 确定有解之后，我们可以尝试输出组合

。

r[1][100] 有解，而第 1 题的分数为 1，那么有两种情况，如果 r[2][100] 有解，那么组合中可以没有第 1 题，如果 r[2][99] 有解，那么组合中可以有第 1 题。总之，这两种情况至少有一种满足，才会使 r[1][100] 有解。

伪代码： 

void printResults(Stack<Integer> stack, int index, int sum)
{
    ...

    // 当前问题有解
    如果 r[index][sum] == true
        // 组合中没有第 index 题
        |-- 如果 r[index + 1][sum] == true
            |-- printResults(stack, index + 1, sum);
        // 组合中有第 index 题    
        |-- 如果 sum - scores[index] >= 0 且 r[index + 1][sum - scores[index]] == true
            |-- stack.push(index);
            |-- printResults(stack, index + 1, division);
            |-- stack.pop();
}

以上是打印组合是的递推公式，我们还要考虑边界情况： 

void printResults(Stack<Integer> stack, int index, int sum)
{
    如果 sum <= 0
        |-- 打印 stack

    // 迭代到了表格的第一行，要么是这一行有解，要么是 n == 1
    如果 index == n
        // 这一行有解
        如果 score[n] == sum
            |-- stack.push(n);
            |-- 打印 stack
            |-- stack.pop();
            |-- return;  
        // n == 1，小明只找到了一个题目，且这个题目的分数不等于 SUM  
        否则
            |-- return;
    ...
}

综上，Java 代码如下： 

public static void findSumN() {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[] scores = new int[n];
//        for (int i = 0; i < n; i++) {
//            scores[i] = in.nextInt();
//        }

    int n = 7;
    int[] scores = {0, 1, 2, 4, 8, 16, 32, 64};

    boolean[][] r = new boolean[n + 1][SUM + 1];
    markResults(n, scores, r);
    printResults(n, scores, r);
}

/*
3
3
6
7
*/

private static void printResults(int n, int[] scores, boolean[][] r) {
    Deque<Integer> stack = new ArrayDeque<>(n);

    printResults(n, scores, r, stack, 1, SUM);
}

private static void printResults(int n, int[] scores, boolean[][] r,
                                 Deque<Integer> stack, int index, int sum) {
    if (sum == 0) {
        printStack(stack);
    }

    if (index == n) {
        if (r[index][sum]) {
            stack.push(index);
            printStack(stack);
            stack.pop();
        }
        return;
    }

    if (r[index][sum]) {
        if (r[index + 1][sum]) {
            printResults(n, scores, r, stack, index + 1, sum);
        }
        int division = sum - scores[index];
        if (division >= 0 && r[index + 1][division]) {
            stack.push(index);
            printResults(n, scores, r, stack, index + 1, division);
            stack.pop();
        }
    }
}

private static void printStack(Deque<Integer> stack) {
    if (stack.size() == 0) {
        return;
    }
    System.out.println(stack.size());
    Iterator<Integer> iterator = stack.descendingIterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

private static void markResults(int n, int[] scores, boolean[][] r) {
    for (int j = 1; j <= SUM; j++) {
        r[n][j] = false;
    }
    r[n][0] = true;
    r[n][scores[n]] = true;

    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j <= SUM; j++) {
            if (r[i + 1][j]) {
                r[i][j] = true;
                if (j <= SUM - scores[i]) {
                    r[i][j + scores[i]] = true;
                }
            }
        }
    }

}


Tags: