编程思维训练 - 递归、滑动窗口、动态规划

最近一个朋友需要通过一个考试，拉着我一起做了一些题，虽然有些题目有点晦涩难懂，看起来没啥实用价值。但越做越发现这些题确实对编程思维、逻辑会有一定的训练。这里把最近做题的一些收获，简单的和大家分享下，希望对大家有帮助。

本文主要从新手的角度出发，以普通人的理解能力来介绍一些入门级算法思维

先来一道热身题

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

普通解法 O(n²)

• 普通解法思路：使用两层循环遍历出所有 a，b 可能的场景，逐一计算比较，找到 target 值，返回对应 index 数组
• 时间复杂度: O(n²)

var twoSum = function (nums, target) {
  let len = nums.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

一层循环解法 O(n)

• 优化思路：一层循环遍历时，a、b 会经历两次遍历，这是突破口。增加一个对象，存储之前已经遍历过的值的下标 obj[nums[index]] = index。如果有发现当前遍历项 obj[target - nums[index]] 不为 undefined，就说明找到匹配项了。一层遍历就可以解决
• 时间复杂度：O(n)

var twoSum = function (nums, target) {
  let len = nums.length;
  let obj = {} // js 直接用对象代替 hash 表
  for (let i = 0; i < len; i++) {
    if (obj[target - nums[i]] !== undefined) {
      return [i, obj[target - nums[i]]]
    }
    obj[nums[i]] = i
  }
}

• 来源：1. 两数之和 - 力扣
• 同题型练习：5242. 兼具大小写的最好英文字母
• 扩展思考：15. 三数之和

斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。 示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

递归解法

var fib = function(n) {
   if (n <= 1) {
       return n
   }
   return fib(n - 1) + fib(n - 2)
}

记忆化递归解法

可以想象 f(5) = f(4) + f(3); f(4) = f(3) + f(2); 这里面 f(3) 会重复计算，整个递归过程可能有很多这种重复项。

记忆化递归的思路就是使用一个变量，将之前递归了的，缓存结果，不重复递归，减少递归次数。

let cache = {}
var fib = function(n) {
   if (n <= 1) {
       return n
   }
   if (cache[n]) {
       return cache[n]
   }
   let result = fib(n - 1) + fib(n - 2)
   cache[n] = result
   return result
}

递归栈溢出问题

递归会保存上一次的状态，会占用栈空间，而这个空间一般是有限的，如果死循环，或者循环比较多，可能会有栈溢出（stack overflow）问题。

可以用浏览器测试：打开浏览器 F12 将以上递归函数 copy 到 Console，执行 fib(100000)，会看到如下错误

那对于计算第 10 万个数，还有非递归的解法吗？下面来看动态规划解法

动态规划解法

思路：从 0, 1, 2 ... 100 一次计算值，并用数组存结果，一直到 n。复杂度 O(n)

动态规划英文是 Dynamic Programming (DP) 直译动态编程，优化后翻译是动态规划。

可以简单的理解为，使用一维数组或二维数组存储之前的计算结果，用于后面的计算。它把复杂问题分解为相互依赖的更小子问题来解决。

注意: DP 与分而治之的区别在于，分而治之是把问题分解为独立的子问题，然后组合他们的答案。

var fib = function(n) {
    let dp = [0, 1]
    if (n <= 1) {
        return dp[n]
    }
    for (let i = 2, len = n; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

再来试试，看是否会报错

节省空间 DP

上面实现中，我们缓存了所有 0 - n 结果，我们只需要最后的结果，可以，用三个临时变量存储结果，减少存储空间

var fib = function(n) {
    if (n <= 1) {
        return n
    }
    let pre1 = 0, pre2 = 1, result = 0;
    for (let i = 2; i <= n; i++) {
        result = pre1 + pre2
        pre1 = pre2
        pre2 = result
    }
    return result
}

矩阵快速幂与通项公式

以上解法是 O(n) 复杂度，使用下面的数学方法，可以使复杂度更低

1. 矩阵快速幂 - 复杂度 O(logn) 递推关系：

只要能快速计算矩阵 M 的 n 次幂，就可以得到 F(n) 的值。如果直接求取 M 的 n 次方，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 M 的 n 次方的求取。

// 来源：力扣官方题解
var fib = function(n) {
    if (n < 2) {
        return n;
    }
    const q = [[1, 1], [1, 0]];
    const res = pow(q, n - 1);
    return res[0][0];
};

const pow = (a, n) => {
    let ret = [[1, 0], [0, 1]];
    while (n > 0) {
        if ((n & 1) === 1) {
            ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}

const multiply = (a, b) => {
    const c = new Array(2).fill(0).map(() => new Array(2).fill(0));
    for (let i = 0; i < 2; i++) {
        for (let j = 0; j < 2; j++) {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
        }
    }
    return c;
}

2. 通项公式

// 通项公式看 Math.pow 性能， 缺点 fib(20) 6765.000000000005，浮点计算不准确，可 Math.round(result)
// 公式推导：https://baike.baidu.com/item/斐波那契数列/99145
var fib = function(n) {
    return (Math.pow((1 + Math.pow(5, 0.5)) / 2, n) - Math.pow((1 - Math.pow(5, 0.5)) / 2, n)) /  Math.pow(5, 0.5)
}

爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这里需要用逆向思维，爬到第 n 个台阶，只有两种方法：

1. 从 n-1 台阶爬一个台阶，这种情况爬到 n，总共有 sum(n-1) 种方法
2. 从 n-2 台阶爬两个台阶，这种情况爬到 n，总共有 sum(n-2) 种方法

因此 sum(n) = sum(n - 1) + sum(n -2)，即也是一个斐波那契数数列。解法基本同上。

猴子跳阶梯问题

尝试实现同类型扩展题

1. 一天一只顽猴想要从山脚爬到山顶
2. 途中经过一个有n个台阶的阶梯，但是这个猴子有个习惯，每一次只跳1步或3步
3. 试问猴子通过这个阶梯有多少种不同的跳跃方式

• 来源：509. 斐波那契数 - 力扣
• 来源：70. 爬楼梯
• 推荐：植物中隐藏的数学—— 斐波那契数列是什么？李永乐老师讲神奇的斐波那契数列

递归与地图

对于一些地图类问题，二维数组结合递归可以很好的解决，比如扫雷游戏、病毒扩散计算、机器人走迷宫等

扫雷

学会了递归后，大家可以尝试实现一个扫雷。思路：用二维数组表示地图，核心递归逻辑：一扫一大片功能

// 部分核心代码，c语言实现
int mark[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; // 8个方向坐标
char map[NUM][NUM] = {0}; // 内部地图
void zero_digui(int x, int y) // 递归显示
{
    ui[x-1][y-1] = 0 + 48;
    int x1 = 0, y1 = 0;
    for (int i = 0; i < 8; i++) { // 遍历周围的8个方向
        x1 = x + mark[i][0];
        y1 = y + mark[i][1];
        if (x1 < 1 || x1 > NUM || y1 < 1 || y1 > NUM) continue; // 如果超出了边界
        int count = lei_count(x1,y1,NUM); // 计算当前坐标周围有多少雷
        if (count != 0) ui[x1-1][y1-1] = count + 48; // 不为0直接写值 
        else if (ui[x1-1][y1-1] == '0') continue; // 为0, 但值已是0，以前遍历过
        else zero_digui(x1,y1); // 为0，没遍历过, 遍历
    }
}

机器人走迷宫

题目描述

1. 房间由 X*Y 的方格组成，6*4 的大小。每一个方格以坐标（x,y）描述。
2. 机器人固定从方格（0，0）出发，只能向东或者向北前进。出口固定为房间的最东北角，如下图的方格（5，3）.用力保证机器人可以从入口走到出口。
3. 房间有些方格是墙壁，如（4，1），机器人不能经过哪儿。
4. 有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。有些地方是机器人无法到达的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。
5. 如图中 陷阱方格有 2 个 不可达方格有 3 个。
6. 请为该机器人实现路径规划功能：给定房间大小，墙壁位置，请计算出陷阱方格与不可达方格分别有多少个

输入描述

1. 第一行为房间的 X 跟 Y （0<X,Y<=1000）
2. 第二行为房间中的墙壁的个数 N （0<=N<X*Y）
3. 接着下面会有N行墙壁的坐标同一行中如果有多个数据以一个空格隔开，用例保证所有数据合法（结尾不带回车换行）

输出描述

1. 陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开

示例：

# 输入
6 4   # 房间 x, y
5     # 墙壁个数
0 2   # 墙壁坐标
1 2
2 2
4 1
5 1

# 输出
2 3

递归思路：

• 和爬楼梯类似，使用逆向思维，从终点倒推，可以到达终点的点。依次递归标记（可到达终点）并计数，递归完成（坐标都越界）后，就可以计算出陷阱（不能到达终点的点个数）方格个数；
• 同样的方法，正向递归标记，就可以计算出不可达（不能从起点到达的点）方格数量。
• 这里递归有点特殊，向上、向右两个方向都需要递归，注意退出条件

function getTrapAndUnreachable(x, y, wallList) {
  // 生成 x * y 二维数组，并设置墙
  const getMap = () => {
    let mapList = new Array(x)
    for (let i = 0; i < x; i++) {
      mapList[i] = new Array(y).fill('')
    }
    wallList.forEach(([x, y])=> {
      // console.log(x, y)
      mapList[x][y] = 'wall'
    })
    console.log(mapList)
    return mapList
  }
  
  let mapList = getMap()
  let reachable = 0
  // 从终点遍历，能够到达终点的点
  const backSearchFill = (x, y) => {
    mapList[x][y] = 'reachable' // 必定可达
    reachable++ // reachable 数++
    // x, y 可到达终点，则左(x - 1, y)、下(x, y - 1)都可达
    // console.log(x, y,[x - 1, y], [x, y - 1])
    if (x - 1 < 0 && y - 1 < 0) {
      return // 如果左下两个坐标不满足条件，直接退出
    }
    // 左侧查找, 如果左边(x - 1, y)没超出坐标范围，且不是墙, 标记可达，并继续向下递归寻找
    if (x - 1 >= 0 && !['wall', 'reachable'].includes(mapList[x - 1][y])) {
      backSearchFill(x - 1, y)
    }
    // 下查找（根据上面的规律：在范围内，不是墙）
    if (y - 1 >= 0 && !['wall', 'reachable'].includes(mapList[x][y-1])) {
      backSearchFill(x, y - 1)
    } else {
      return
    }
  }
  backSearchFill(x - 1, y - 1)
  let trapCount = x * y - reachable - wallList.length
  console.log(mapList, `陷阱（不能到达终点的点个数）：${trapCount}`)
  
  // 重新初始化
  mapList = getMap()
  reachable = 0
  let maxX = x - 1;
  let maxY = y - 1;
  // 从起点遍历，能够从起点到达的点
  const frontSearchFill = (x, y) =>  {
    mapList[x][y] = 'reachable' // 必定可达
    reachable++ // reachable 数++
    // x, y 能够从起点达到，则右(x + 1, y)、上(x, y + 1)都能从起点到达
    // console.log(x, y,[x + 1, y], [x, y + 1])
    if (x + 1 > maxX && y + 1 > maxY) {
      return // 如果左下两个坐标不满足条件，直接退出
    }
    // 右侧查找, 如果右边(x + 1, y)没超出坐标范围，且不是墙, 且没标记为可达，并继续向下递归寻找
    if (x + 1 <= maxX && !['wall', 'reachable'].includes(mapList[x + 1][y])) {
      frontSearchFill(x + 1, y)
    }
    // 上查找（根据上面的规律：在范围内，不是墙）
    if (y + 1 <= maxY && !['wall', 'reachable'].includes(mapList[x][y + 1])) {
      frontSearchFill(x, y + 1)
    } else {
      return
    }
  }
  frontSearchFill(0, 0)
  let unreachableCount = x * y - reachable - wallList.length
  console.log(mapList, `不可达（不能从起点到达的点）：${unreachableCount}`)
  
  console.log(trapCount, unreachableCount)
}

console.log(getTrapAndUnreachable(6, 4, [[0, 2], [1, 2], [2,2], [4,1], [5,1]]))
// [
//     [ '', '', 'wall', '' ],
//     [ '', '', 'wall', '' ],
//     [ '', '', 'wall', '' ],
//     [ '', '', '', '' ],    
//     [ '', 'wall', '', '' ],
//     [ '', 'wall', '', '' ] 
//   ]
//   [
//     [ 'reachable', 'reachable', 'wall', 'reachable' ],
//     [ 'reachable', 'reachable', 'wall', 'reachable' ],
//     [ 'reachable', 'reachable', 'wall', 'reachable' ],
//     [ 'reachable', 'reachable', 'reachable', 'reachable' ],
//     [ '', 'wall', 'reachable', 'reachable' ],
//     [ '', 'wall', 'reachable', 'reachable' ]
//   ] 陷阱（不能到达终点的点个数）：2
//   [
//     [ '', '', 'wall', '' ],
//     [ '', '', 'wall', '' ],
//     [ '', '', 'wall', '' ],
//     [ '', '', '', '' ],
//     [ '', 'wall', '', '' ],
//     [ '', 'wall', '', '' ]
//   ]
//   [
//     [ 'reachable', 'reachable', 'wall', '' ],
//     [ 'reachable', 'reachable', 'wall', '' ],
//     [ 'reachable', 'reachable', 'wall', '' ],
//     [ 'reachable', 'reachable', 'reachable', 'reachable' ],
//     [ 'reachable', 'wall', 'reachable', 'reachable' ],
//     [ 'reachable', 'wall', 'reachable', 'reachable' ]
//   ] 不可达（不能从起点到达的点）：3
//   2 3

思考其他思路：图的搜索，深度优先搜索（DFS）与广度优先搜索（BFS）？

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

暴力穷举法 - pass 99% 超时

常规思维来看，两层 for 循环遍历字符串开始下标、结束下标，可以列出所有可能，再判断是否有重复字符串，判断重复一层循环，就有三层循环了。

// 986 / 987 个通过测试用例，最后一个超时
var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) {
    return s.length
  }
  let maxLen = 0;
  const hasRepeat = (str) => {
    let charCountObj = {}
    for (let i = 0, len = str.length; i < len; i++) {
      let item = str[i]
      if (charCountObj[item]) {
        return true
      } else {
        charCountObj[item] = 1
      }
    }
    return false
  }
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      let str = s.substring(i, j + 1);
      if (maxLen >= str.length || hasRepeat(str)) {
        continue
      }
      maxLen = str.length
    }
  }
  return maxLen
};

穷举加缓存 - pass 99% 超出内存

优化点：根据记忆化递归思路，判重时，如果之前已经判断过该字符串，直接从缓存取，可以减少第三层循环的次数，但会增加空间复杂度，代码如下，但又报内容超了。。。

// 986 / 987 个通过测试用例 - 超过内容限制
var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) {
    return s.length
  }
  let maxLen = 0;
  let cacheHasRepeat = {} // 缓存之前已经判重后的结果
  const hasRepeat = (str) => {
    // 如果有缓存直接使用缓存结果，减少重复遍历
    if (cacheHasRepeat[str] !== undefined) {
      return cacheHasRepeat[str]
    }
    let charCountObj = {}
    for (let i = 0, len = str.length; i < len; i++) {
      let item = str[i]
      if (charCountObj[item]) {
        cacheHasRepeat[str] = true // 缓存结果
        return true
      } else {
        charCountObj[item] = 1
      }
    }
    cacheHasRepeat[str] = false // 缓存结果
    return false
  }
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      let str = s.substring(i, j + 1);
      if (maxLen >= str.length || hasRepeat(str)) {
        continue
      }
      maxLen = str.length
    }
  }
  return maxLen
};

滑动窗口解法 - AC耗时500ms

两层循环解法，获取以 str[i] 开头的最大不重复子串

"abcabcbb"

以 (a)bcabcbb 开头的最长子串为 (abc)abcbb

以 a(b)cabcbb 开头的最长子串为 a(bca)bcbb

以 ab(c)abcbb 开头的最长子串为 ab(cab)cbb

以 abc(a)bcbb 开头的最长子串为 abc(abc)bb

...

以 abcabcb(b) 开头的最长子串为 abcabcb(b)

之前我们用了第三层循环，来判断是否是不重复的子串，这里我们可以利用第二层循环来记录字符出现次数，就不需要第三层循环了，代码如下

var lengthOfLongestSubstring = function (s) {
  // 滑动窗口解法
  if (s.length <= 1) {
    return s.length
  }
  let longest = 0
  // (a)bcabcbb
  for (let i = 0, len = s.length; i < len; i++) {
      let charObj = { [s[i]]: 1 } // 存储字符出现次数 { a : 1 }
      let max = 1
      for (let j = i + 1; j < s.length; j++) {
          if (charObj[s[j]]) { // 有值，说明重复了，跳出循环
              break; 
          } else {
              // 没重复的，编辑字符出现次数为 1
              charObj[s[j]] = 1
              max++
          }
      }
     (max > longest) && (longest = max)
  }
  return longest
}

将缓存值 charObj 对象改为 Set 集合，会更快

优化后的滑动窗口 80ms

上面答案虽然可以通过，但还有优化的空间，如果 s 为 "abcdea"

假设从 k 位置开始（"a"），判断到最长子串时，坐标位置为 rk（"e"）

下次循环 k + 1 位置开始("b")，我们又从 k+1+1 ("c")开始去判断了，并没有利用之前的结果 rk。("e")

理论上，如果 k ~ rk （"a"到"e"）没重复，那么 k+1 到 rk ("b"到"e")也没重复。我们只需要扩大 rk 范围即可。可减少循环次数

var lengthOfLongestSubstring = function(s) {
    if (s.length <= 1) {
        return s.length
    }
    let longest = 0
    let charSet = new Set()
    let rk = 1 // 右指针 index
    for (let i = 0, len = s.length; i < len; i++) {
        // 第一次遍历，规规矩矩
        if (i === 0) {
            charSet.add(s[i]) // "abcdea" 中的 "a"
        } else {
            // 利用上一次结果, 开启下一次判断
            // 假设第二次，从 "b" 开始,  把上次循环重复的 "a" 移除
            // 第二次 rk 还是上次的 5，不用从 b 的后一位重复判断
            charSet.delete(s[i - 1])
        }
        
        // 没走到字符串末尾，且没有重复的
        while(rk < len && !charSet.has(s.charAt(rk))) {
            // 添加到无重复集合
            charSet.add(s.charAt(rk), 1)
            // 右指针偏移 +1
            rk++
        }
        // i = 0; "a - e"，rk 为最后一个 "a" 的值，5,5 - 0 为 5
        ((rk - i) > longest) && (longest = rk - i)
    }
    return longest
};

• 来源：3. 无重复字符的最长子串 - 力扣
• 扩展练习: 30. 串联所有单词的子串

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。 示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

`1 <= coins.length <= 12`
`1 <= coins[i] <= 231 - 1`
`0 <= amount <= 104`

穷举所有情况

对于 coins 为 [1, 2, 5]，amount 为 11 的场景，所有场景包括

1. 全为 1
2. 全为 2
3. 全为 5
4. 1 2 组合， 个数比例遍历
5. 1 5 组合， 个数比例遍历
6. 2 5 组合，个数比例遍历
7. 1 2 5 组合， 个数比例遍历

硬币面额有 3 种时，要全部穷举，需要上面这么多次遍历，这里 coins 最大为 12, 要列出所有情况逻辑会很多，显然要换个思路。

换个思路，我们这里要找的最少硬币数

最少硬币数，是否意味着尽量多用最大面额，再依次选小面额？

不一定，比如 [1,5,11] 硬币，凑 15 的场景

15=1×11+4×1，硬币数 5 个

15=3×5，硬币数 3 个

似乎无从下手，那要怎么去解决这种问题呢？

取巧的递归方法

思路：递归时，可以遍历硬币数组，逐一减去对应硬币面额，递归函数用一个参数累加硬币数 +1，就是总硬币数，取最小值

以 [1, 2, 5] 11 为例

递归函数：f(金额, 当前使用硬币数)，步骤分解

# 金额11,硬币数0 => for循环依次减去硬币面额,硬币数+1 => 继续减,硬币+1
f(11, 0) => -1 f(10, 1) => -1 f(9, 2) => .. f(x, 3)
                        => -2 f(8, 2)
                        => -5 f(5, 2)
         => -2 f(9, 1) => -1 f(8, 2)
                       => -2 f(7, 2)
                       => -5 f(4, 2)
         => -5 f(6, 1) => -1 f(5, 2)
                       => -2 f(4, 2) => for(1,2,5),硬币+1...
                       => -5 f(1, 2) => -1 f(0, 3) // ok比最小值
                                     => -2 f(-1, 3) 退出循环

将上面的推导，转化为代码如下

var coinChange = function(coins, amount) {
    if (amount === 0) {
        return 0
    }
    let min = Infinity
    const f = (sum, count) => {
        // 为负数时，表示走不通
        if (sum < 0) {
            return 
        }
        // 可以拼凑成功
        if (sum === 0) {
            count < min && (min = count)
            return count
        }
        for (let i = 0, len = coins.length; i < len; i++) {
            f(sum - coins[i], count+1)
        }
    }
    f(amount, 0)
    // 如果找不到
    if (min === Infinity) {
        return -1
    }
    return min
};

这种方法是 OK 的，但如果目标金额大，递归容易超时

15 / 189 个通过测试用例
[1,2,5] 100 超出时间限制

记忆化递归

使用记忆化递归优化，需要改变思路，递归需要有返回值，f(amount, 0) 函数需要返回最小硬币数，这样才能使用缓存数据。感觉不好理解，有兴趣的可以去看看这种解法：零钱兑换题解

动态规划 DP

我们可以使用动态规划试试，1、尝试分解子问题 2.用数组存结果

上面是至上而下的遍历。我们可以使用菲波那切数列的 dp 思维

以 [1, 2, 5] 11 为例

# f(金额) 为 凑成金额所需的最小硬币数
f(0) = 0
# f(金额) = 1 + 其中硬币最小值 (f(金额-1), f(金额-2), f(金额-5))
f(1) = 消耗 1 硬币 + Min(f(0), f(-1), f(-4)）= 1 + min(0 ,-1,-1) 
f(2) = 消耗 1 硬币 + Min(f(1), f(0), f(-3)) = 1 + min(1, 0, -1)
f(3) = 消耗 1 硬币 + Min(f(2), f(1), f(-2)) = 1 + min(1, 1, -1)
f(4) = 消耗 1 硬币 + Min(f(3), f(2), f(-1)) = 1 + min(2, 1, -1)
f(5) = 消耗 1 硬币 + Min(f(4), f(3), f(0)) = ...
f(6) = 消耗 1 硬币 + Min(f(5), f(4), f(1)) = ...
...
f(11) = 消耗 1 硬币 + Min(f(10), f(8), f(6))

因此 f(n) = 1 + Min(f(n-硬币1),f(n-硬币2),..f(n-硬币))

转换成代码

var coinChange = function(coins, amount) {
    if (amount === 0) {
        return 0
    }
    let dp = [0]
    // dp(1) => dp(2) => dp(3) => ... dp(n)
    for (let i = 1; i <= amount; i++) {
        let min = Infinity
        // 遍历所有减去 1 个硬币后的值，找最小值， -1 忽略
        for (let j = 0, len = coins.length; j < len; j++) {
            let count = dp[i - coins[j]]
            // 负数时直接忽略
            if (count < 0) {
                continue
            }
            // 0 或 其他值
            if (count < min) {
                min = count
            }
        } 
        // 如果是 Infinity，则为 -1
        if (min === Infinity) {
            dp[i] = -1
        } else {
            dp[i] = min + 1
        }
    }
    return dp[amount]
};

可以 AC 了，但貌似时间稍微长，从比较好理解的角度来讲，感觉不好在优化了。如果大佬有易懂的更优解，欢迎评论区讨论。

• 来源：322. 零钱兑换 - 力扣
• 扩展练习：494. 目标和、背包问题

参考

• 题库 - 力扣
• 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
• 学习 JavaScript 数据结构与算法（第三版）p265