都2024年了，还不会动态规划吗？我教你！🚀🚀🚀

文章同步在公众号：萌萌哒草头将军，欢迎关注

本系列文章

早些年一听到动态规划，我头就迅速变大，因为一直以为动态规划是种高端的算法，一开始就觉得自己学不会，只要提起来我就不自觉得开始抵触。

其实随着工作中一点点的积累，使我慢慢意识到，我已经在不知不觉中使用了动态规划的思想，例如，实习的时候，我负责知识图谱的绘制，知识图谱是由一系列节点和边组成的。而这些节点的层级可能深。

后端返回给我的是扁平数据结构：

interface Node {
    id: string;
}
interface Edge {
    source: string;
    target: string;
}
let nodes: Node[] = [A, B, C, D, E]
let edges: Edge[] = [A -> B, A -> C, B -> D, D -> E]

虽然绘制的时候组件会自动格式化数据

import { graph } from "graph"
graph.init({ nodes, edges})

但是我的任务是负责交互，需要点击节点隐藏子节点，或者展示子节点，

我的第一种方案是：点击节点时，是使用递归方式，寻找所有子节点，然后隐藏或者展示。

function findAllDescendants(nodeId: string): string[] {
    let descendants: string[] = [];
    for (const edge of edges) {
        if (edge.source === nodeId) {
            descendants.push(edge.target);
            
            descendants.push(...findAllDescendants(edge.target));
        }
    }

    return descendants;
}

功能虽然没问题了，但是想想每次点击都要在全量数据上使用递归查找子节点，哪怕是同一个节点，刚刚点击为展示，过一会又点击为隐藏，每次都重新计算未免太浪费了。

所以我的第二种方案是: 每次节点如果第一次点击，我先使用递归算法，获取该节点的所有子节点，保存在map中，下次点击该节点，先从map中获取结果，没有值，则使用递归方法查询，返回结果同时保存这次的查询结果。

let mome= {}
function findAllDescendants(nodeId: string): string[] {
    
    if (memo[nodeId]) {
        return memo[nodeId];
    }

    
    let descendants: string[] = [];
    for (const edge of edges) {
        if (edge.source === nodeId) {
            descendants.push(edge.target);
            
            descendants.push(...findAllDescendants(edge.target));
        }
    }

    
    memo[nodeId] = descendants
    
    return descendants;
}

let data = {
    A: [B, C, D, E],
    B: [D, E],
    C: [],
    D: [E],
    E: []
}

这种技巧，我在后来的工作中经常用到。

直到有一天，我了解了一个名词：记忆化搜索，

这个词的意思是：在递归的过程中将已知的信息保存起来，下次直接使用，避免重复计算。

直到这时，我才恍然大悟，原来我已经掌握了递归的改良版本!

然而此时，谷歌或者百度记忆化搜索，都会连带出相关词：动态规划！

那么它俩之间有啥联系呢？这个问题得从递归说起！

我们知道递归是将一个大问题，拆解成多个重复的子问题，解决子问题之后，大问题也就迎刃而解了。

例如经典的裴波那契数列求和：

我们要计算fn(5)的值，需要知道fn(4)的值，要知道fn(4)的值，需要知道fn(3)的值……

使用递归计算方法如下：

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

其计算过程演示如下：（图地址：zhuanlan.zhihu.com/p/438406757…

我们可以发现fn(3)重复计算了两次，fn(2)重复计算了3次。

我们使用记忆化搜索优化这个问题：

let memo = {}
function fibonacci(n) {
  if (memo[n]) return memo[n]
  if (n <= 1) {
    return n;
  }
  let result = fibonacci(n - 1) + fibonacci(n - 2)
  memo[n] = result
  return result;
}

是不是觉得这样已经很棒了，但是要知道，函数调用也是有开销的，即使使用了记忆化搜索，在遇到递归层级很深的时候，依然会面临很大的内存开销。

那有没有什么方法避免递归中大量的函数调用呢？答案是存在的。

递归递归，是先将大问题传递下去成为小问题，然后在从小问题回归到大问题。

那么我们是不是可以直接从小问题开始”回归”，遇到我们想要的结果再停下来？

这就是递归和动态规划的主要区别之一（思维方式的区别）

下面是从底层直接开始的写法：

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  let sums = new Array(n + 1).fill(0);
  sums[1] = 1;
  for (let i = 2; i <= n; i++) {
    sums[i] = sums[i - 1] + sums[i - 2];
  }
  return sums[n];
}

由于第一项的和为0，第二项的和为1，所以从第三项（下标是2）开始，直到第n项结束。就是我们需要结果了。

我们知道，在这个算法中，第i项的值为第i-1和第i-2项的和，所以我们可以轻松的写出这个公式：

sums[i] = sums[i - 1] + sums[i - 2];

而这个公式在动态规划里有个专有名词：状态转移方程（Dynamic Programming，简称DP）

也是将大问题分解为小问题的关键。通常使用DP表示。所以通常会写成下面的样子，

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  let dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

好，总结下，到这里，我们已经知道了递归的缺点：

• 函数大量调用开销
• 存在大量重复计算的问题

并且知道

• 使用记忆化搜索改良递归重复计算的问题
• 使用动态规划从已知的小问题入手，逐步解决大问题，来解决递归的函数大量调用的开销问题。

下篇文章，我会详细介绍动态规划的一些经典问题和解题思路，最后记得关注我的公众号：萌萌哒草头将军