将暴力递归改为动态规划

回溯，动态规划，贪心，分治是刷题过程中最常见的几个算法，其中回溯和动态规划又是更加常见且存在千丝万缕联系的两种。以LeetCode 算法题按标签分类的统计的前15个标签(截止2021年05月13日)：

我们知道回溯，深度优先搜索 各自对应的是一种算法，在实现的时候他们多半都是通过递归来实现的，这样深度优先搜索 + 回溯 加起来涉及题目数量将进一步提升到前列的一个位置。 递归 与 动态规划的重要性可见一般。正是基于这种重要性，笔者才不惜时间花费整理输出了这篇文章。

常规动态规划解法

正常的我们在拿到一个问题，使用动态规划解法去做的时候，一般都会经历下面这几个步骤：

① 分析问题，找出问题根据规模或者下标位置变化时的相邻规模或者位置之间的关联 ② 若能够根据尝试中使用的规模或者位置找出关联则进一步的写出状态转移方程，若不能则回到①再尝试 ③ 得到状态转移方程之后，由转移方程中牵涉变量定义出状态转移表(dp表，一位二维或者更高维度) ④ 根据题意初始化dp表，并由状态转移方程迭代完成dp表剩余部分的计算 ⑤ 按问题所求，找到dp表对应位置的结果返回

上面步骤只是一般步骤，不包括对动态规划的优化后的一些该有的描述。 此外上述步骤都是经验所得也看着抽象很空洞和抽象。 下面以选取的两个例子来反应一下这个过程：

以位置建立状态

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 例如： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

根据题设，可以发现小偷走一圈下来，中间的每个位置都可以获取到对应的一个金额，并且相邻位置的金额是有关联的，在找关联之前，我们先做如下定义

f(i) 代表 i 位置能获取到的金额，其中i ∈[0,n-1] , n为数组长度

a. 对于 n < 2 的情况，由于无论怎么选，都只有一种情况就可以当做特例处理。
b. 对于 n >= 2 的情况，可以发现 i 位置能获取到的金额跟路径有关系，在路径上若选择了 i-2 ,那么i-1 就不能选了；类似的若选择了 i-1，那么i-2 和 i位置都不能再选。 根据这种关系可以得到 f(i) 与之前状态转换关系如下：

f(i) = f(i-2) + nums[i] (选择i-2,跳过i-1) f(i-1) (选择i-1,跳过i-2)

到这里状态转移方程就写出来了相当于①②顺利完成，剩下③④⑤就相对容易了，因为这里只用到了一个维度的数据，也就是数组下标。很容易的就能想到定义一个一维数组 dp[]来表示。考虑下标的变化情况可以简单的将数组定义为dp[n+1] ，这样对于任何位置能获取到的最大金额直接就存在了dp表中，要求走完所有数组之后能获取到的最大值，对应的就是dp[n] 的值。

分析到这里其实就可以开始写代码了，回顾分析的过程似乎也比较自然，这当然是因为题设比较简单，我们相对容易的完成了 ①②两步， 对于一些复杂的情况，要定义出能找出状态转移方程的状态是不太容易的，一旦发现不可行再回过头去根据状态转移的特点去憋出一个状态定义是很费脑细胞的事。下面先给出以上分析的代码实现：

    public static int rob(int[] nums) {
        if(nums == null || nums.length < 1)  return 0;
        int len = nums.length;
        int[] max = new int[len + 1];
        max[0] = 0 ;
        max[1] = nums[0];
        for(int i = 2; i <= len; i++){
            max[i] = Math.max(max[i-1] , max[i-2] + nums[i-1]);
        }
        return max[len];
    }

以范围建立状态

考虑如下问题

博弈拿牌问题 假设有这样有一堆牌用int[]nums 表示, 现在有两个人轮流的从牌堆的首尾去拿牌，规定仅能从最前面或者最后面拿，不能从中间抽取，假定每个人都是绝对理性的。最终手上牌数值加起来的总数更大的一方获胜。问获胜方手中牌总数是多少？

题设中绝对理性的含义，指的是每个人在保证自己能拿到更大总数的情况下，会设法让对方拿到更小总数。但是如果没到最后，我们其实是不知道谁手上的牌的总数更大的。 基于这种思考，我们可能会想到最好是能做一下深度优先搜索，然后在回溯的时候做一些拿牌的选择。然后回溯到最开始的位置就能获得一个值，这个值是啥？ 可以是获胜方累积的总数吗？

确实不太好回答这个问题，那么就先来尝试一下这个过程，看看能不能发现一些规律：

设牌的数量为 n 当 n = 1 时 ， 先拿的获胜，对应的总数就是牌面值 当 n = 2 时， 先拿的选择其中的较大值，因此也是先拿的获胜 当 n = 3 时， 先拿的可以选择从左拿或者从右拿，但是他没办法一开始就拿中间的 那如果牌堆的数值是 3，100，5 这种情况，先拿的人是没办法获胜的，因为不管拿3还是拿5，中间的100 会被对方拿走。 这也可以看出牌的面值，牌的数量和分部情况决定了获胜方是谁以及获胜方手中牌面值总和。

那么对于剩余牌的总数量为 i 的情况下，先拿的选手能获取到的总数量可以表示成 f(i) 吗？ 答案是不行， 因为剩余数量为 i ，对应在牌堆中可能有多种情况，也就是说剩下拿i张牌是要看两个人具体是怎么拿的，这个和牌的分部有关。说明当前问题并不能以位置来建立状态。 事实上如果以牌的左右位置的下标标识的范围建立状态，就可以很好的描述问题了。 譬如定义先拿选手的状态为 f(i,j) , 后拿选手状态为 h(i,j) .

且慢，这里为什么针对两个选手，分别定义了他们的状态，这样做和直接用一个状态标识最大值是不是有点背离？ 事实上，因为每个选手拿的牌和上一个选手所做的选择有关，如果混沌的以一个状态标识，中间的过程会显得复杂。而如果分别标识每个选手的拿牌状态，最终的获胜方和拿牌更多的牌数只需要简单的比较一些就能得到，另外一个重要的好处就在于，通过建立两个状态或许能把这中间的过程提现的更清楚。

接着分析， 那么 f(i,j) 代表当前选手直接从 下标范围为 [i,j] 的牌堆中取牌，那么他现在的选择和总数最大怎么建立关联呢？ 答案是他没有选择，因为他只能取左边或者右边的牌，能做得选择就是在从左边或者右边选的时候找出更大的那个方案，然后选择更大的方案。 也就是说先拿的选手也不能保证自己拿到总数更大的拿一手牌，而是每次拿都去比较出更大的那个并选择它。所以：

f(i,j) =Math.max( nums[i] + h(i+1， j) , nums[j] + h(i,j-1))

为什么是上面的写法？ 怎么还依赖上了后拿选手的状态？ 确实是这样，如果不依赖的话我们会发现由于后拿选手做了选择，被依赖状态如果用f() 来表示的话， 每种选择下有对应的依赖两种不确定结果的更大值，表述将会更加复杂。 那么上述 h(i+1, j） 和 h(i,j-1) 分别对应的含义呢

h(i+1,j) 面对范围为 [i+1,j] 的牌， 后拿的人能获取到的总数最大的值 h(i,j-1) ….

这就很好理解了， 作为先拿的人，在拿完后再次拿的时候，他就变成了后拿的人了，所以上述f(i,j) 是这样一个依赖关系。那对于后拿的人，他在h(i,j) 时的状态依赖呢？从实际含义上来讲，既然都是后拿了，肯定是先拿的人留下的更小的那个结果了？为什么是更小的那个结果—因为两个人分一堆牌，先拿的已经在按自己能拿的最多的情况在做选择了，总数一定的情况下，后拿的自然就是更小的那个选择。 所以

h(i,j) = Math.min( f(i+1,j) , f(i,j-1) )

需要注意的有这么几个地方：

① 后拿的选手并没有真正的从 (i，j) 范围内取牌，他是在对方拿了之后才能取，所有没有直接依赖到牌面值 ② 对于后拿的选手来讲，如果面对的是 f(i+1,j) , f(i,j-1) 两个，他为什么选更小的那个？ —- 不是他选的，是对方帮他选的。怎么理解这里的对方帮他选呢？ 来看一个例子 假设 nums = {6,50,100,8} 共四张牌 那么对于后那选手 h(0,3) 他最近的能拿到哪张牌呢？肯定是 50 ，因为先手会先选择6 ，而不是8 ， 那么对应在h(i,j) 的表达式中就是先手留给了后拿选手 f(1,3) 而不是 f(0,2) 也就是说h(0,3) = Math.min(f(1,3), f(0,2))

经此分析，如果用动态规划的方法来解决问题的话，状态转移方程也出来了。那么对应的动态规划初始值和返回结果呢？
— 这种情况下，动态规划需要是一个一张二维表来保存状态转移的结果，表中最大的值即为所求。
那么对应的初始值呢？
— i,j 标识的范围可以看出，表中i > j 的范围内都为 0，这部分数据不符合实际含义。 i == j 部分的数据都为对应的 nums[i].

到这里我们就可以开始写动态规划的代码了：

    public static int cardLineWinnerSum(int[]nums){
        if(null == nums || nums.length == 0) return 0;
        int len = nums.length;
        int[][] former = new int[len][len];
        int[][] latter = new int[len][len];
        for(int i = 0 ; i < len ; i++){
            former[i][i] = nums[i];
            latter[i][i] = 0;
        }
        // 填表former 和 latter
        for(int k = 1 ; k < len ; k++){
            for(int j = k , i = 0; j < len ; i++,j++){
                former[i][j] = Math.max(nums[i] + latter[i+1][j], nums[j] + latter[i][j-1]);
                latter[i][j] = Math.min(former[i+1][j],former[i][j-1]);
            }
        }
        // 最大值在 former 或者 latter 的右上角
        int maxSum = former[0][len-1] > latter[0][len-1] ? former[0][len-1] : latter[0][len-1];
        return maxSum;
    }

问题递归解法

还是前面的问题，这次我们尝试用递归的方式来解决一下，看看这个过程是否更容易(要有信心绝大多数的循环都可以改为递归实现)。对比上面的实现，我们可以在比较中看到哪种更加符合我们的自然思维。

对于《打家劫舍》，若用递归的方式解决，递归的方法定义(主要是传参和返参) 的选择就变得很重要了。 这里也需要我们去做一些尝试，然后边写边调整。在此之前先做一些分析

若返回数值就是能获取的最大金额，那么这个金额需要在递归的时候就要比较出来，那么等递归的归的过程返回时拿到的就是必然是最大值。然后我们在递归调用过程中需要知道当前到了什么位置，这样传参除了数组 nums 之外还需要有一个 index 记录当前到了什么位置。这样似乎在参数上面就差不多了， 剩下就是递归终止条件 和具体实现。对于下标在走的情况，终止条件显然的就是下标到达最后位置了，根据情况可以是越界，也可以是最后一个元素的位置。 下面来具体分析一下

(1) 终止条件
终止条件作为递归的出口，在对输入数组做遍历时，index 可以是递增的方向，也可以是递减的方向。对应的在终止条件的判断上就会不一样。按本题的题设，若是沿着index 递增的方向，那么对应的终止条件就是
“index >= nums.length” , 类似的若是按照递减的方向终止条件就将是 “index < 0” , 两者都可以。 只不过对应的递归函数在调用时就会存在差异。 前者通过 dfsRob(nums,0) 调用， 后者使用 dfsRob(nums,nums.length-1)调用。

(2) 位置为 i 对应最大金额
在递归调用时，每一层都有自己的最大金额的计算方式，而且每一层计算方式都相同，这就类似于动态规划的状态转移方程了。这里以从后向前遍历的为例，写出来就像下面这样：

    private static int dfsRob(int[]nums,int index){
        if(index < 0) return 0;
        int skip = dfsRob(nums,index-1);
        int rob = nums[index] + dfsRob(nums,index-2);
        return Math.max(skip,rob);
    }

然后 最重要的是，我们看上面这个代码，相当于就是说，我这次抢了接下来就跳过一家继续做选择，如果我这次没有抢，那么就在紧接着的下一家继续做选择，这种描述其实是非常符合问题向我们阐述的限制条件的。相当于把那句话直接转化成了代码。 上面这样写会有几个问题老生常谈的问题
a) 存在重复计算的问题，这个可以通过调用树看出来，如下图以计算f(4) 为例
b) 若数组长度太长，容易导致栈溢出，这是递归调用相比循环调用特有的

因此这类存在重复计算的递归调用(这里对应回溯算法) 在数据规模较大时性能会很低或者索性就不可行了。解决办法也是一个是加备忘录，记录下来每个计算过的位置的值，每次计算前先查一遍备忘录。但这仍然是递归调用，还是受栈空间的限制。

对于《博弈拿牌》问题的递归解法，前面范围f(i,j) 与 h(i,j) 之间的关系同动态规划实现，递归写法上只需要对应的考虑终止条件，以及返回值计算 和 递归方法调用方式即可。

• 由于递归调用时，范围是一个变小的过程，因此 最终只需要判断 i==j 就可以返回了，这对于先手拿牌和后手拿牌都是一样的，不同之处在于先手返回是nums[i] , 而后手返回的是 0
• 返回值的计算就是f(i,j) 和 h(i,j) 对应的依赖关系
• 按题设一开始调用的范围都是以数组中的首末位置的下标作为 i 和 j ，因此调用方式分别为f(0,len-1), h(0,len-1)

    public static int findCardLineWinner(int[]nums){
        if(null == nums || nums.length == 0) return 0;
        int former = former(nums, 0, nums.length - 1);
        int latter = latter(nums, 0, nums.length - 1);
        return former > latter ? former :  latter;
    }
    public static int former(int[]nums ,int l,int r){
        if(l == r){
            return nums[l];
        }
        int c1 = nums[l] + latter(nums,l+1,r);
        int c2 = nums[r] + latter(nums, l,r-1);
        return Math.max(c1,c2);
    }
    /**
     * 作为后手取牌,实际取牌拿到的牌是对方选择后的
     */
    public static int latter(int[]nums , int l ,int r){
        if(l == r){
            return 0;
        }
        int f1 = former(nums, l + 1, r);
        int f2 = former(nums, l, r - 1);
        return Math.min(f1,f2);
    }

最终代码的实现可以简单的看成是对限制条件和状态关系的直接翻译，这里就不做过多的解读。重点还是在于，如果拿到上面的递归实现，我们是否可以轻松的改造为动态规划的做法。

递归解法转动态规划

对于在递归调用时相邻参数之间存在关联的情况，我们可以将这种参数组合转化为缓存内部数据的关联关系。 简单来说其实还是使用一个存储空间用来备忘(动态规划就是一种以空间换时间的解决方案)，但是它不仅仅是记录每个位置的值，而是需要通过前面计算出来的值进一步的计算出当前位置的值，这样通过纯粹的操作缓存中的数据就能找出所有位置的值。然后要求的结果就是这个缓存表里取其中一个即可。

以《打家劫舍》的递归代码为例，这里为了方便查看，把代码再贴出来一下

    private static int dfsRob(int[]nums,int index){
        if(index < 0) return 0;
        int skip = dfsRob(nums,index-1);
        int rob = nums[index] + dfsRob(nums,index-2);
        return Math.max(skip,rob);
    }

根据如上代码，可以看到可变参数就只有 index 一个，而且变化范围在 [0,nums.length) 内 因此改造时定义一个一维的缓存表dp ,dp的大小需要根据index的变化范围来确定，对于以上代码 我们发现若index < 0,对应的还需要返回0，这中越界情况下也要反应到 dp表中来，因此dp的范围要比 nums 的大1 。于是有:

int dp = new int[nums.length+1]

另外 index < 0 时 对应在dp 中不能是dp[-1] , 这种写法在java 中是不支持的而且也违反实际含义。 所以在这里我们还需要做一个约定

dp[0] 代表 index 为-1 位置， 那么dp[1] 对应的才是index = 0 的位置

这样一来，我们的dp 表就可以准确的表达上述递归代码中的index 变化了。因此有如下初始值

dp[0] = 0 ;
dp[1] = nums[0];

最后看index 变化与返回值的关系，可以看到 index 是递减发现逼近终止条件的，这个是递归的”递”的过程，等到 “归”的时候，其实index 是从小到大的变化回去的, 这时index 是从-1 一直增加到 nums.length-1。而对于 index 譬如等于 n 时的返回值，对应的就是dp[n+1] , 那么这个dp[n+1] 的取值，通过将如下三行

int skip = dfsRob(nums,index-1);
int rob = nums[index] + dfsRob(nums,index-2);
return Math.max(skip,rob);

就能得到直观的结果，首先 dfsRob(nums,index-1) (index = n)非常直观的我们可以知道它就对应 dp[n], 类似的 dfsRob(nums,index-2) 对应dp[n-1]，那么dp[n+1]的计算方式自然就是

dp[n+1] = Math.max(dp[n], dp[n-1] + nums[n])

最后看一下返回结果，由于递归调用时的传参是 dfsRob(nums,nums.length-1) , 由于dp数组对应位置要比 index 大1，因此 dp[nums.length] 即为待返回结果。

汇总以上分析，得到转化后的代码如下：

    public static int rob(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1];
        dp[0] = 0 ;
        dp[1] = nums[0];
        for(int i = 2; i <= len; i++){
            max[i] = Math.max(max[i-1] , max[i-2] + nums[i-1]);
        }
        return max[len];
    }

这里和直接应用动态规划来解是一样的，这种先写递归写法再应用动态规划来做的好处在于，若问题比较复杂，动态规划的状态转移方程不能快速想出来。那多先应用递归实现再改为动态规划可以让我们很稳的写出动态规划的解法。

《博弈拿牌》问题的递归实现由于定义了两个递归方法，每个方法在递归时都依赖了另一个方法，这种交错式的递归在改为动态规划时需要分别将每个递归方法按参数组合情况定义dp缓存表。

如上图，由于先手和后手在终止条件上得到的返回值并不相同，因此这里对角线上的初始化值也存在差异。根据递归实现的如下相互依赖关系：

   public static int former(int[]nums ,int l,int r){
        if(l == r){
            return nums[l];
        }
        int c1 = nums[l] + latter(nums,l+1,r);
        int c2 = nums[r] + latter(nums, l,r-1);
        return Math.max(c1,c2);
    }
    public static int latter(int[]nums , int l ,int r){
        if(l == r){
            return 0;
        }
        int f1 = former(nums, l + 1, r);
        int f2 = former(nums, l, r - 1);
        return Math.min(f1,f2);
    }

在初始化两个二维表格时，先手需要依赖的后手的左边和下边的元素，因此对于这种情况，在写dp表时我们需要以对角线的方向作为初始化数据的方向，并且先手和后手的dp表在写的时候要相互交错，因为他们彼此互相依赖。最终改造实现的代码同直接使用动态规划实现。

    public static int cardLineWinnerSum(int[]nums){
        if(null == nums || nums.length == 0) return 0;
        int len = nums.length;
        int[][] former = new int[len][len];
        int[][] latter = new int[len][len];
        for(int i = 0 ; i < len ; i++){
            former[i][i] = nums[i];
        }
        // 填表former 和 latter
        for(int k = 1 ; k < len ; k++){
            for(int j = k , i = 0; j < len ; i++,j++){
                former[i][j] = Math.max(nums[i] + latter[i+1][j], nums[j] + latter[i][j-1]);
                latter[i][j] = Math.min(former[i+1][j],former[i][j-1]);
            }
        }
        // 最大值在 former 或者 latter 的右上角
        int maxSum = former[0][len-1] > latter[0][len-1] ? former[0][len-1] : latter[0][len-1];
        return maxSum;
    }

改造原则总结

常见的几种尝试模型

(1) 从左往右的尝试模型
(2) 范围上的尝试模型
(3) 多样本位置全对应的尝试模型
(4) 寻找业务限制的尝试模型

递归过程设计原则

(1) 每一个可变参数的类型，不要比int类型更复杂
(2) 若违反原则1，让类型突破到一维线性结构，则该参数必须是唯一参数
(3) 若唯一的可变参数是一维线性结构,只需要做到记忆化搜索即可
(4) 可变参数的个数，能少则尽量少

递归到动态规划改造套路

(1) 获取到不违反原则的暴力递归的过程时，而递归过程存在解得重复调用
(2) 找到哪些参数变化会影响返回值,对每一个列出变化范围
(3) 参数间的所有组合数量，意味着表的大小
(4) 记忆化搜索的方法就是用简单缓存来存数据
(5) 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
(6) 对于有枚举行为的决策过程，需要进一步优化