从典例开始了解动态规划的前世今生

问: 有4种面值为1，5，10，25的货币，可以重复使用，需要凑成1000元，问共有多少种货币组成方案？
分析问题:

  • 当使用0张面值为5元的货币，剩下由{1，10，25}组成1000元的方案总数计为 res1
  • 当使用1张面值为5元的货币，剩下由{1,10,25}组成的995元的方案总数计为 res2
  • …
  • 当使用199张面值为5元的货币，剩下由{1,10,25}组成的5元的方案总数计为 res200
  • 当使用200张面值为5元的货币，剩下由{1,10,25}组成的0元的方案总数计为 res201

上述求方案总数的方法都会用到一个递归函数。
那么这里总的方案数为上述结果的累加，即: res1 + res2 + … + res201

这里就可以定义这个递归函数: int(int[] arr, index , aim);
这个递归函数表示的含义是如果用arr[index … N-1] 的面值货币组成的 aim 目标钱数的方案总数
于是就可以得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
private int violence(int[] source, int index, int aim) {
    int res = 0;  // 方案总数
    if(index == source.length){
        res = aim == 0 ? 1 : 0; // aim 为 0 表示这种方案可行，所以res = 1; 结果累加即可
    }else{
        for(int i = 0; source[index] * i <= aim ; i++){
            // 固定一种货币情况下的递归函数求计算总数
            res += violence(source,index ++ , aim -  source[index] * i);
        }
    }
    return res;
}

这种方法又叫暴力搜索算法。但是有个重复计算的问题，比如说在已经使用0张5元和1张10元的情况下，会求volience(source,2,990)的值。当使用2张5元和0张10元的情况下，也会求一次violence(source,2,990)的值。这就造成了重复计算的问题，这种问题在这个题目中出现的次数非常之多，所以我们需要将这些计算过结果的情况保存下来，所以出现了下面将要介绍的记忆搜索算法。

这里的记忆搜索算法的记忆是怎么实现的呢？需要怎样记忆？记忆什么内容？这些问题将是我们需要进一步探讨的。
从上面的分析可知，因为source参数是不变的，只有index和aim值是变化的。所以我们需要记忆的就是violence(index, aim)的值。有两个可变参数，所以我们用一个二维数组的map来记忆这个值。记为 int[][] map = new int[i][j];
i 为index 的大小 +1 ，j 为 aim的大小 + 1。 map[i][j]的值就表示当index = i， aim = j的情况时的方案总数。代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int memory(int[] source, int index, int aim,int[][] map) {
    int res = 0; 
    if(index == source.length){
        res = aim == 0 ? 1 : 0; 
    }else{
        int mapValue = 0;
        for(int i = 0; source[index] * i <= aim ; i++){
            mapValue = map[index + 1][aim-source[index]*i];
            if(mapValue != 0){
                res += mapValue == -1 ? 0 : mapValue;
            }else{
                res += violence(source,index ++ , aim -  source[index] * i);
            }
        }
    }
    map[index][aim] = res == 0 ? -1 : res;
    return res;
}

上面的这个记忆搜索算法就相当于动态规划的一种形态了。下面讲讲两者的区别和联系:

  • 记忆搜索不关心达到某一个递归过程的路径，只是单纯的对计算过的递归过程进行记录，避免重复递归的过程。
  • 动态规划严格规定了到达目标的路径，只能依次计算得到结果。后面的结果严格依赖前面的计算结果。
  • 两者都是用空间换时间的做法，也都有枚举的过程，一个有顺序，一个没顺序。

就多了一个有顺序的枚举过程，为什么一定要去学动态规划呢？那正是因为有顺序的枚举，才有了可以优化算法的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int dpm(int[ ] source, int aim, int[][] dp){
    dp[0][0] = 1;
    for(int i=0;i<dp.length;i++){
        dp[i][0] = 1;
        for(int j=1;j<dp[0].length;j++){
            if( i == 0 ){
                dp[i][j] = (j % source[i] == 0) ? 1 : 0;
            }else{
                // 未优化
                // for(int k = 0; k <= aim / source[i] && (j - source[i] * k) >= 0; k++){
                //     dp[i][j] += dp[i-1][j - source[i]*k ];
                // }
                // 优化后，少了枚举过程
                dp[i][j] = dp[i-1][j];
                dp[i][j] += (j - source[i] >= 0) ? dp[i][j - source[i]] : 0 ;
            }
        }
    }
    return dp[source.length-1][aim];
}

具体的动态规划过程参考动态规划（1）

Read More

默认配图