二十一、动态规划

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

1.动态规划：备忘录和状态转移方程

动态规划（Dynamic Programming）是一种常用的算法设计和优化技术，广泛应用于解决各种优化问题。它的核心思想是将复杂问题分解为相互重叠的子问题，并通过记忆化搜索和状态转移来高效地求解问题。在动态规划中，备忘录和状态转移方程是两个重要的概念。

1）备忘录

备忘录是动态规划中的一种优化技术，用于避免重复计算子问题。当我们解决一个问题时，往往会遇到许多重复的子问题。如果我们每次都重新计算这些子问题，那么计算量将会非常大。为了避免重复计算，我们可以使用备忘录来记录已经计算过的子问题的结果，以便在需要时直接查找并返回结果，而不必重新计算。

备忘录可以使用数组、哈希表或其他数据结构来存储子问题的结果。一般来说，我们可以使用一个一维或多维数组来构建备忘录。备忘录的初始化值通常是一个特殊的标识，表示该子问题尚未计算过。在计算子问题的过程中，我们可以先检查备忘录，如果发现该子问题已经计算过，直接返回备忘录中的结果；否则，我们进行计算，并将结果存入备忘录中。

下面是一个通用的备忘录模板：

function memoizedDP(...) {
  // 初始化备忘录
  const memo = new Array(...);
  function dp(...) {
    if (已经计算过该子问题) {
      return 从备忘录中返回结果;
    }    // 计算子问题
    const result = ...;    // 将结果存入备忘录
memo[...] = result;
    return result;
  }
  return dp(...);
}

2）状态转移方程

状态转移方程是动态规划中的另一个重要概念，用于描述子问题之间的关系。它是动态规划问题的核心思想之一。通过定义状态转移方程，我们可以将原始问题划分为若干个子问题，并找到它们之间的递推关系。

状态转移方程通常用数学公式或逻辑表达式表示。它描述了问题的当前状态和下一个状态之间的转移方式。通过递推计算，我们可以从初始状态逐步推导出最终的解。

在使用状态转移方程求解问题时，一般需要注意以下几点：

• 定义状态：确定问题的状态，即表示问题的变量或参数。状态可以是一维、二维甚至多维的，具体根据问题的特点来确定。
  
• 初始状态：确定问题的初始状态，即起始条件。
  
• 状态转移方程：根据问题的递推关系，描述当前状态和下一个状态之间的转移方式。这通常是问题的核心部分，需要仔细分析问题的特点和规律。
  
• 边界条件：定义问题的边界条件，即最小规模的子问题的解。边界条件通常是已知的，可以直接计算得出。
  

3）动态规划算法框架

动态规划算法可以用以下框架来解决问题：

function dynamicProgramming(...) {
  // 初始化备忘录
  const memo = new Array(...);  function dp(...) {
    // 边界条件
    if (达到边界条件) {
      return 边界条件的结果;
    }    // 检查备忘录
    if (已经计算过该子问题) {
      return 从备忘录中返回结果;
    }    // 根据状态转移方程计算子问题
    const result = 根据状态转移方程计算;    // 将结果存入备忘录
memo[...] = result;
    return result;
  }
  return dp(...);
}

通过以上算法框架，我们可以将原始问题划分为多个子问题，并通过备忘录和状态转移方程高效地求解问题。其中，备忘录用于避免重复计算子问题，而状态转移方程描述了子问题之间的关系，帮助我们逐步求解最终的解。

带你读《图解算法小抄》二十一、动态规划（2）https://developer.aliyun.com/article/1347964