几个有趣的动态规划

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

找零钱练习题
#

给定一个零钱数组比如[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张…，然后计算剩下的总数和剩下的堆数方法总数和。

这个算法也可以优化成记忆搜索，总共有多少种方法拼钱，主要与index和aim有关，我们只要用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];
  
}

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