动态规划是解决一些特定类型的在多项式时间问题的技术。动态编程解决方案比指数暴力方法更快，并且可以很容易地证明它们的正确性。在我们研究如何动态思考问题之前，我们需要知道以下两点：

• 重叠的子问题

• 最优子结构性质

确定它是否是动态规划问题

• 通常，可以通过使用动态编程来解决需要最大化或最小化某些数量或计数问题的所有问题，这些问题用于计算在特定条件下的排列或某些概率问题。

• 所有动态编程问题都满足重叠子问题属性，大多数经典动态问题也满足最优子结构属性。有时我们在给定的问题中观察这些属性，确保它可以使用动态规划思路来解决。

确定问题中的状态变量

动态规划问题都与状态及其转移有关。这是必须非常细心完成的最基本的步骤，因为状态转移取决于所做的状态定义的选择。那么，让我们看看状态到底是什么意思。

状态 :一个状态可以定义为一组的可以唯一识别的特定位置，或在给定的问题中的参数。这组参数应尽可能小，以减少状态空间。

例如：在著名的背包问题中，通过两个参数索引和权重来定义状态，即pack[index] [weight]。这里pack[index] [weight]告诉我们通过从0到具有袋重量的索引的项目可以获得的最大利润。因此，这里参数索引和权重一起可以唯一地识别背包问题的子问题。

因此，我们的第一步是在确定问题是DP问题后决定问题的状态。我们知道DP就是使用计算结果来制定最终结果，所以下一步将是找到先前状态之间的关系以达到当前状态。

通过状态转移关系建立表达式

这里举个例子，借助leetcode上面的习题来吧，下面是问题的详细内容：

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

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

注意：给定 n 是一个正整数。



示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶


示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

接下来用动态规划的方式思考这个问题。首先，决定给定问题的状态，将采用参数n来决定状态，因为它可以唯一地识别任何子问题，接下来将用T(n)来表示一个阶段的状态变量。

现在，我们需要计算T(n)。到底该怎么来计算呢？注意看里面的括号，其代表上一个子结果的状态量。

• 先看只有一层台阶的情况，也就是n=1

1. 1阶

很明显只有一层阶梯，所以T(1) = 1

• 先看只有两层台阶的情况

1.  (1 阶) + 1 阶
2.  2 阶
所以T(2) = 2

• 再来看看三层台阶的情况

1.  (1 阶 + 1 阶) + 1 阶
2.  (1 阶) + 2 阶
3.  (2 阶) + 1 阶
T(3) = 3

• 不太清楚再来看看四层台阶的情况

1.  (1 阶 + 1 阶 + 1 阶) + 1阶
2.  (1 阶 + 2 阶) + 1阶
3.  (2 阶 + 1 阶) + 1阶
4.  (1阶 + 1 阶) + 2阶
5. （2阶）+ 2阶
T(4) = 5

现在再仔细去思考其中的问题，有没有看到对应的关系，就拿第四层台阶来说吧，根据上一次台阶可以知道要么是前一层台阶上1阶，要么是前两层上2阶

T(4) = T(3) + T(2)

所以用参数表明就可以得到下面的状态转移表达式

T(n) = T(n-1) + T(n-2) 需满足n>2

下面用代码实现编写表达式的实现。

func climbStairs(n int) int{
   if n == 1 {
      return 1
   }
   if n == 2{
      return 2
   }
   return climbStairs(n-1)+climbStairs(n-2)
}

保存子问题结果优化解决方案

这是动态编程解决方案中最简单的部分。因为之前的状态计算是呈指数增长，所以我们需要存储状态变量，以便下次需要该状态时，可以直接在内存中使用它。 用代表实现示例如下：

func climbStairs(n int) int {
   if n == 1 {
      return 1
   }
   if n == 2 {
      return 2
   }
   memo := make(map[int]int)
   memo[1] = 1
   memo[2] = 2
   for i := 3; i <= n; i++ {
      memo[i] = memo[i-1] + memo[i-2]
   }
   return memo[n]
}