1. 什么是动态规划

动态规划 (Dynamic Programming 简称 DP) 被定义为一种在多项式时间内解决某些特定类型问题的技术。动态规划的解决方案比指数暴力法更快，并且可以很容易地证明其正确性。

多项式时间如 O(n^2)
指数时间如 O(2^n)

动态规划主要是对普通递归的优化。 每当看到递归(相同的输入被重复调用)，我们都可以使用动态规划对其进行优化。
核心思想是简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。这种简单的优化将时间复杂度从指数级降低到多项式级。

2. 动态规划的特点

动态规划 (DP) 是解决某一类问题的最强大的技术之一。
思维过程相对简单，并且编码部分非常容易。
核心思想: 在用给定的输入解决问题后，将结果保存以供将来使用，这样你就不必重新解决它。简单地说"记住你的过去"。
动态规划问题的特点：如果给定的问题可以分解成更小的子问题，并且这些更小的子问题可以分解成更小的子问题，并且在这个过程中，你会看到一些重叠的子问题。
动态规划2种处理方式：子问题的解存储在表或数组中(memoization) 或以自下而上的方式(tabulation)来避免冗余计算。
动态规划问题可以通过递归公式来解(或者称为转移方程), 当然我们也可以不用递归，但是它的公式是递归的，通常我们使用迭代来实现。

3. 动态规划和贪心算法有什么区别？

动态规划和贪心算法都是用于处理最优解问题

使用贪婪方法，我们执行预定义的流程以获得最佳结果。该流程已知是最佳的。我们按照考虑好的流程来获得最好的结果。

如kruskals算法一样，找到最小成本生成树总是选择最小成本边，这给了我们最好的结果。

或者dijkstra最短路径算法,总是选择我们的最短路径顶点并继续展开顶点以获得最短路径，所以这是一个预定义的过程。
但在动态规划中，我们试图找出所有可能的解决方案，然后选择最佳解决方案，最优解决方案。这种做法是不同的。

4. 动态规划的实现

在了解接下来的两个术语的定义之前，请想象以下场景：

版本1：我会从网上学习DP的理论，然后我会练习一些DP问题，从而掌握DP。
版本2：要掌握DP，我必须练习一些DP问题–> 首先，我必须从网上学习DP的理论

两个版本说的是同一件事，区别仅在于传达信息的方式，而这正是 Bottom-Up 和 Top-Down DP 所做的。

版本 1 可以与 Bottom-Up DP 相关，Version-2 可以与 Top-Down DP 相关。

4.1 记忆法-Top-Down(Memoization)

以计算斐波那契数列为例

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

func FbDpTopDown(n int) int {
   if n <= 1 {
      return 1
   }

   v, ok := Memoization[n]
   if ok {
      return v
   }

   v = FbDpTopDown(n-2) + FbDpTopDown(n-1)
   Memoization[n] = v
   return v
}

4.2 制表法 Bottom-Up(Tabulation)

以计算斐波那契数列为例

func FbDpBottomUp(n int) int {
   dp := make([]int, n+1)
   dp[0] = 1
   dp[1] = 1
   for i := 2; i <= n; i++ {
      dp[i] = dp[i-1] + dp[i-2]
   }
   return dp[n]
}

4.3 记忆法、制表法对比

	Tabulation	Memoization
状态	状态转移关系较难思考	状态转移关系简单
编码	条件较多时编码复杂	编码简单、不复杂
速度	快, 直接从表格访问上一个状态	慢，递归调用函数消耗
子问题的解	如果必须至少解决所有子问题一次，则自下而上的动态规划算法通常比自上而下的记忆算法好一个常数因子	如果子问题空间中的一些子问题根本不需要解决，记忆解决方案的优点是只解决那些确实需要解决的子问题
入口	在 Tabulated 版本中，从第一个子问题开始，所有子问题都被逐条填充	与 Tabulated 版本不同，所有子问题不一定在 Memoized 版本中填充, 而是按需填充
实现方法	通常，Tabulated 是一种迭代方法	Memoization是一种递归方法。

5. 如何解决动态规划问题？

开始处理问题前，首先我们要检查动态规划的2个必要条件

重叠子问题：当需要重复解决相同子问题来解决实际问题时。称为：该问题具有重叠的子问题属性。

这一点可以想想前面斐波那契数列的问题

最优子结构性质：如果给定问题的最优解可以通过使用其子问题的最优解得到，则称该问题具有最优子结构性质。

5.1 解决问题的步骤

识别这是不是一个动态规划问题
用最少的参数定义状态
制定状态和转换关系(也称状态转移方程)
使用tabulation或者memorization方式实现算法

十大常用算法之动态规划-简介