一个文笔一般，想到哪是哪的唯心论前端小白。

前言

最近疯狂的迷上了去力扣上找找存在感。在22 题的位置卡住了，琢磨了好几天都没有实现自己的解决方案。

不得已之下，看了解题结果，大神们的解题思路也是五花八门。最让我感兴趣还是那个老大难--【动态规划】。

原来一直从同事或者其他人的口中听说过这个概念，但是一直因为种种原因没有进一步的去学习这个东西，刚好趁着这道简单题目就初窥一下这个被广大网民疯狂推崇的【动态规划】。

先简单介绍一下这个题目：

思路拆解

因为这道题比较靠前，所以各路大神在这块杀的是难解难分。我只简单说一下我能看懂的思路。

暴力拆解

疯狂的递归出所有的组合方式，然后过滤掉重复的，再过滤掉不满足有效的，然后得出结论。

插入

将每一对括号作为一个整体去插入到原来的字符串中，因为基础的字符串一直是有效的，只需要去重就好了。

动态规划

在暴力拆解的递归过程中，将不可用的过滤掉，来优化排列组合，可以有效的避免越到后期遍历条数越多的情况。

动态规划去解题

因为本文是在初窥动态规划，所以更多的视角是如何理解动态规划这个概念，跟解题其实干系不大。

我理解的动态规划的核心是动态两个字，在递归的过程中，动态的修改每次递归的入参，将不合要求的项提前处理掉，从而来提高递归效率。

可能有点片面，只能符合某一类场景。但是，其实最最最核心的点就是如何搜集不合要求的项，有些场景是需要搜集最终的一个结果，有些场景是需要搜集整条链路，有些场景是需要搜集链路中的某一项的全量信息。所以如何去搜集就是每个场景需要去单独考虑的事情了。

因为这个题目是做括号()，在解题过程中打印的信息可能不准，所以我做了一个变换。

题目，现有一个长度为 n 的数组，里面每一项是正整数，请输出由所有的组合方式中满足2的倍数的的项，每一项都要用到。

测试用例： [1,2,3,4]。

第一步：排列组合

可以考虑一下实现一个排列组合的方法，这个是解题的基础结构。

先说一下我的生成思路：

使用递归的方法去生成所有的组合方式： 第一次的结果：12 13 14 21 23 24 31 32 34 41 42 43 长度为 4x3=12 第二次的结果：123 124 132 134 142 143 ... 长度为 4x3x2=24 第三次的结果：1234 1243 1424 ... 长度为 4x3x2x1=24 其实就是 n 的阶乘的实现方式

下面这个方法是我涉及的一个递归方法，用来生成给定的数组的所有组合方式。

/*
 * @params {arr: number[]} 给定的数组 
 * @params {result: number[][]} 上一次递归的结果 
 * @params {time: number} 自增次数，用来统计递归层级，方便跳出 
 */
function recurArr(arr, result = [...arr.map((item) => [item])], time = 1) {
    console.log(time);
    let _r = [];
    if (time < arr.length) {
      for (let item of result) {
        const _arr = arr.filter((e) => !item.includes(e)); // 不包含已选过的数据
        for (let a of _arr) {
          _r.push([...item, a]);  
        }
      }
      time++;
      return recurArr(arr, _r, time);
    } else {
      return result;
    }
  }
  
  recurArr([1,2,3,4]);

如上代码，我们就得到了所有的排列组合方式，现在就可以使用 filter 去过滤掉不满足 2 的倍数的结果了。然而这个并不是我们要的思路，因为我们要规划一下它。从而提高他的效率！！！

第二步：规划

我们想一下，既然结果要的是2的倍数，那么所有的排列组合的过程中数字的最后一位就必须是 2 或者 4，所以我们就可以把 result 每一项的顺序调过来，每次都往前插，这样效率就提高了一倍。

// 修改入参，默认 result 是由满足 2 的倍数的项组成的二维数组
function recurArr(arr, result = [...arr.filter(item => item% 2 === 0).map((item) => [item])], time = 1) {
    console.log(time);
    let _r = [];
    if (time < arr.length) {
      for (let item of result) {
        const _arr = arr.filter((e) => !item.includes(e)); 
        for (let a of _arr) {
         _r.push([a, ...item]);   // 修改插入顺序
        }
      }
      time++;
      return recurArr(arr, _r, time);
    } else {
      return result.map(item => item.toReversed()); // 返回正序的排序
    }
  }
  
  recurArr([1,2,3,4]);

如上就实现了一个简单易懂的动态规划的 demo。

回归正题

力扣原题中要的是满足有效的括号。

那么每次递归中，不满足的条件就是：已选结果中，右括号比左括号多。

每次递归的时候把不满足的过滤掉就好了。

总结

下面纯属个人理解，并附带大神的讲解地址。

所谓动态规划其实是一个线性的处理过程，每一次的执行都可以理解为一个独立的场景，但是这个场景除了处理过程一致，周围的环境都变了。就需要这个程序去智能的结合环境的变化而修改处理的参数。从而达到解决问题的目的。

初窥就到这里了，后面研究一下高级用法，See U ~ ~ ~

算法-动态规划 Dynamic Programming--从菜鸟到老鸟