左小白的技术日常
Github

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

这篇文章发布于 2022/07/31,归类于
标签:
递归滑动窗口动态规划两数之和O(n)解法机器人走迷宫

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

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

先来一道热身题

两数之和

给定一个整数数组 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²)

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)

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
  }
}

斐波那契数

斐波那契数 (通常用 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),会看到如下错误

image.png

那对于计算第 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]
}

再来试试,看是否会报错

image.png

节省空间 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) 递推关系: image.png

只要能快速计算矩阵 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;
}
  1. 通项公式 image.png
// 通项公式看 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 个台阶。你有多少种不同的方法可以爬到楼顶呢?

image.png

这里需要用逆向思维,爬到第 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. 试问猴子通过这个阶梯有多少种不同的跳跃方式

递归与地图

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

扫雷

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

// 部分核心代码,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. 请为该机器人实现路径规划功能:给定房间大小,墙壁位置,请计算出陷阱方格与不可达方格分别有多少个

image.png

输入描述

  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% 超出内存

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

image.png

// 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
};

零钱兑换

给你一个整数数组 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]
};

image.png

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

参考