暴力递归到动态规划--组成额定金额的方法数

对于递归,问题在于其实质为暴力展开,所以会导致重复的操作。通过增设傻缓存记录和动态规划可以优化递归,当元素的依赖数是有限的,比如马跳日,机器人步数等,这时记忆化搜索和动态规划是没多大却别的。
但是当有枚举行为时(即不同格子依赖数各不同),就需要动态规划,因为动态规划还具有优化的余地,如下题。

  • 题目

有一定数目不同面额的货币供选择,每个面额选取数不限,求组成总金额为M的方法数。暴力递归到动态规划--组成额定金额的方法数

  • 分析

1)递归逻辑

比如货币面额放在一个数组,array[2,3,5],表示可供选择的面额有2,3,5。现要求组成10元,有多少中方法。
我们用index表示array中当前位置,rest表示要组成的钱数。即让第index位的面额去填补rest。
暴力递归到动态规划--组成额定金额的方法数
暴力递归到动态规划--组成额定金额的方法数
2)动态规划
·Index和rest可变,先做出一个表格。array[] = {2,3,5}
暴力递归到动态规划--组成额定金额的方法数
dp[index][rest]表示用index及其后面的面值填补rest,故dp[0][10]即为目标。

·接下来看递归
暴力递归到动态规划--组成额定金额的方法数
如dp[1][10]的值会依赖dp[2]这个一行的某些值,如下图,i=0,i=1,i=2,直至越界
即绿色星号的值等于三个绿色的√值的和。
暴力递归到动态规划--组成额定金额的方法数
由于求解的顺序是从左往右(i一开始是0,那么rest-i*array[index]是递增的),所以下图问号的值的求解,是先于绿色星号的。
暴力递归到动态规划--组成额定金额的方法数
可看出问号的值等于前两个√的和。所以绿色星号的值应该依赖于问号,那就不用再去重复累加前两个√的值了。dp[index][rest] = dp[index+1][rest] + dp[index][rest-array[index]]。这就是转移方程。
记忆化所搜索只会去找,而动态规划可以通过分析找出优化的依赖方式。
暴力递归到动态规划--组成额定金额的方法数
暴力递归到动态规划--组成额定金额的方法数
暴力递归到动态规划--组成额定金额的方法数