1. 概念讲解

讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（下文统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，DP其实是一种解决问题的思想。

这种思想的本质是：一个规模比较大的问题（可以用两三个参数表示的问题），可以通过若干规模较小的问题的结果来得到的（通常会寻求到一些特殊的计算逻辑，如求最值等）

所以我们一般看到的状态转移方程，基本都是这样：

opt ：指代特殊的计算逻辑，通常为max or min。

i,j,k 都是在定义DP方程中用到的参数。

dp[i] = opt(dp[i-1])+1

dpi = w(i,j,k) + opt(dpi-1)

dpi = opt(dpi-1 + xi, dpi + yj, ...)

每一个状态转移方程，多少都有一些细微的差别。这个其实很容易理解，世间的关系多了去了，不可能抽象出完全可以套用的公式。所以我个人其实不建议去死记硬背各种类型的状态转移方程。但是DP的题型真的就完全无法掌握，无法归类进行分析吗？我认为不是的。在本系列中，我将由简入深为大家讲解动态规划这个主题。

我们先看上一道最简单的DP题目，熟悉DP的概念：

题目：假设你正在爬楼梯。需要 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 阶

2. 题目图解

通过分析我们可以明确，该题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建。满足“将大问题分解为若干个规模较小的问题”的条件。所以我们令 dp[n] 表示能到达第 n 阶的方法总数，可以得到如下状态转移方程：

dp[n]=dp[n-1]+dp[n-2]

• 上 1 阶台阶：有1种方式。
• 上 2 阶台阶：有1+1和2两种方式。
• 上 3 阶台阶：到达第3阶的方法总数就是到第1阶和第2阶的方法数之和。
• 上 n 阶台阶，到达第n阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。

3. Go语言示例

根据分析，得到代码如下：

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

原文链接：https://segmentfault.com/a/1190000021739367