Contents
  1. 1. 找零钱练习题
    1. 1.1. 正向暴力搜索
    2. 1.2. 反向暴力搜索
    3. 1.3. 反向暴力搜索优化
    4. 1.4. 动态规划
    5. 1.5. 动态规划的优化
  2. 2. 总结

这篇博文是从问题理解动态规划的练习篇,通过几个动态规划的问题剖析进一步理解动态规划

找零钱练习题

  • 给定一个零钱数组比如[1, 2, 5],每个值代表一个面额的纸币,给定一个总数(aim),求换钱有多少种方法(每种面额纸币不限量)

这个问题非常经典,所以我就从最先容易想到的算法出发慢慢推导出动态规划

正向暴力搜索

面前一大堆钱,分成三堆,我们必须要从这三堆中抽取出来所以可能的方案,看看能够凑到总数。

我们第一个想到的就是正向暴力搜索,先从第一堆取出0张、1张、2张….,然后递归下去,让取出0张、1张、2张凑剩下的总数,等到取到最后一个钱堆或者总数正好相同的时候递归停止。

我们可以很轻松的写出下面的代码(Java)

int violenceSearch(int[] level, int index, int aim) {
        if (aim <= 0) {
            return aim == 0 ? 1 : 0;
        }
        if (index >= level.length) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i <= aim / level[index]; i++) {
            sum = sum + violenceSearch(level, index + 1, aim - i * level[index]);
        }
        return sum;
    }

这个函数接受三个参数,第一个是钱堆的面额数组,第二个是当前是拿第几个钱堆的序号,第三个是剩余要凑的总数

这个算法的核心就是sum = sum + violenceSearch(level, index + 1, aim - i * level[index]);,我们分别从钱堆里面取出想0张、1张…,然后计算剩下的总数和剩下的堆数方法总数和。

这个算法也可以优化成记忆搜索,总共有多少种方法拼钱,主要与indexaim有关,我们只要用map记录一下这个值就可以优化成为记忆搜索。

反向暴力搜索

反向的话比较难想到,但是正向暴力搜索没有办法分解成子函数,也就无法实现动态规划,所以我们必须要反向思考

首先我们假设纸币面额为1, 2, 5, 我们要凑10块钱,我们假设已经得到了所以的次数F(x, y)(x为由多少种纸币组成,y为凑多少钱),所以我们得到这个我们想要的结果F(3, 10) (也就是由3种面额组成10块)

假设我们得到了F(3, 10)所以可能的组成结果结合如下面10种

  • 10张1块
  • 8张1块、1张2块
  • 6张1块、2张2块
  • 5张1块、1张5块
  • 4张1块、3张2块
  • 3张1块、1张2块、1张5块
  • 2张1块、4张2块
  • 1张1块、2张2块、1张5块
  • 2张5块
  • 5张2块

现在我们把这10种可能按照5块的张数分成3份

  • 0张5块
    • 10张1块
    • 8张1块、1张2块
    • 6张1块、2张2块
    • 4张1块、3张2块
    • 2张1块、4张2块
    • 5张2块
  • 1张5块
    • 5张1块、1张5块
    • 3张1块、1张2块、1张5块
    • 1张1块、2张2块、1张5块
  • 2张5块
    • 2张5块

分别为0张5块(6种),1张5块(3种),2张5块(1种),也就是我们成功将F(3, 10)分解成 F(2, 10), F(2, 5), F(2, 0)

通过这种方式我们成功构造出子函数,我们很容易就能写出递归函数

int lowBackVS(int[] level, int index, int aim) {
    if (index == 0)
        return aim % level[index] == 0 ? 1 : 0;

    if (aim < level[index]) return lowBackVS(level, index - 1, aim);
    else {
        int count = 0;
        for (int i = 0; i * level[index] <= aim; i++) {
            count += lowBackVS(level, index - 1, aim - i * level[index]);
        }
        return count;
    }
}

这里我们要看到第二个if,我们判断剩下的余额是否够当前的一张,如果不够,那直接就是前n-1种纸币能够组成的次数。(也就是假如你剩下4块钱要用一张5块来组成,肯定不可能,直接返回前面的n-1种货币能够凑出4块的种数)

这种时间复杂度为O(n) = n X aim X aim, 假如aim比较大还是比较耗时间的,我们看看是否能够优化一下

反向暴力搜索优化

我们还是回到上面那个例子,我们这次按照能够减去一张5块的进行分类,这样我们就分成了两类

  • 无法抽掉一张5块
    • 10张1块
    • 8张1块、1张2块
    • 6张1块、2张2块
    • 4张1块、3张2块
    • 2张1块、4张2块
    • 5张2块
  • 能够抽掉一张5块
    • 5张1块、1张5块
    • 3张1块、1张2块、1张5块
    • 1张1块、2张2块、1张5块
    • 2张5块

一张是无法抽掉一张5块(6种),能够抽到一张5块(4)种
我们回到函数定义,这样我们成功将函数F(n, aim)分解成两个F(n-1, aim) 和F(n, aim - level[index])

我们成功的将子函数进行化简成两项

int backVS(int[] level, int index, int aim) {
    if (index == 0)
        return aim % level[index] == 0 ? 1 : 0;

    if (aim >= level[index])
        return backVS(level, index - 1, aim) + backVS(level, index, aim - level[index]);
    else return backVS(level, index - 1, aim);

}

我们可以看到我们成功将时间复杂度降到了O(n) = n X aim,至此我们写出了比较完美的反向暴力搜索方法,当然我们也能够像正向暴力搜索优化成记忆搜索

动态规划

前面我一直没有怎么提记忆搜索法,因为这个方法基本上等同与动态规划,只不过动态规划使用数组存贮,记忆搜索法用字典存贮。

前面我们知道我们能通过分解函数将问题划分成前面的子问题,所以我们只需要构建一个二维数组,x,y分别代表由几种货币组成(index),组成的总数(aim),这样就能通过慢慢“填”写动态规划表,最后求出由N种货币组成钱数(aim)总数

int dynamic(int[] level, int index, int aim) {
    int n = level.length;
    int[][] dp = new int[n][aim + 1];
    for (int i = 0; i < n; i++) dp[i][0] = 1;
    for (int i = 1; i <= aim; i++) dp[0][i] = i % level[0] == 0 ? 1 : 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= aim; j++) {
            if (j < level[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i - 1][j] + dp[i][j - level[i]];
        }
    }
    return dp[n - 1][aim];

}

这里要注意的是初值的初始化,默认当钱数为0的时候值为1(比如说前面的2张5块的方法F(2, 0) = 1),当只由一种钱币组成时,只要总数能够整除第一种钱币面额就为1(全部由这种货币组成)

动态规划的优化

当然这个优化可有可无,因为我们观察上面的函数,我们发现其实N层只与前面N-1层一个有关,这样的话,我们如果覆盖掉上一层的值对后面的计算结果也没有影响。所以我们就不使用多维数组,直接使用一维数组,节省了(N-1)* (aim + 1)的空间

int advanceDynamic(int[] level, int index, int aim) {
    int[] f = new int[aim + 1];
    f[0] = 1;
    int n = level.length;
    for (int i = 0; i < n; ++i)
        for (int j = level[i]; j <= aim; ++j)
            f[j] += f[j - level[i]];
    return f[aim];
}

所以我们成功的将代码改的更短,而且更省空间

总结

一开始本来想多讲几道动态规划的问题,但是写着写着发现其实大部分都是大同小异,找到子函数,构建表存贮计算过程,其中最大的挑战就是找到分解子函数,所以我就不介绍其他的问题了,我就把这些问题留在下面,你可以试试挑战一下自己

一个背包有一定的承重cap,有N件物品,每件都有自己的价值,记录在数组v中,也都有自己的重量,记录在数组w中,每件物品只能选择要装入背包还是不装入背包,要求在不超过背包承重的前提下,选出物品的总价值最大。

  • 最优编辑

    对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。

  • LIS

求出序列的最长上升子序列的长度

  • LCS

给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A=”1A2C3D4B56”,B=”B1D23CA45B6A”,”123456”或者”12C4B6”都是最长公共子序列。

  • 走迷宫问题

有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。

Contents
  1. 1. 找零钱练习题
    1. 1.1. 正向暴力搜索
    2. 1.2. 反向暴力搜索
    3. 1.3. 反向暴力搜索优化
    4. 1.4. 动态规划
    5. 1.5. 动态规划的优化
  2. 2. 总结