C++ 算法入门：一维动态规划基础实战
动态规划概述
通过大量练习总结出的动态规划做题步骤，可以理解为：某种状态的公式 + 提前求出来值的容器，求出当前位置的值然后放到容器中供后续使用。因为最开始的值一般是可见的，所以能确定初始值，从而启动动态规划。
主要提炼出以下要素：
- 状态
- 容器的重要性
- 公式（即状态转移方程）
严格来说：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 状态存储（容器）
动态规划基本步骤
- 状态表示：就是 dp 表（容器一般是数组）中里面的
dp[i]值的含义。- 通常以 i 位置结尾或开头。
- 分析问题的过程中，发现相同的子问题。
- 状态转移方程：本质就是
dp[i] = ?（也是最难的一步）。- 根据状态表示结合题目含义推导
dp[i]的值。
- 根据状态表示结合题目含义推导
- 初始化：
- 保证填表的时候不越界。
- 主要也是根据题目进行。
- 填表顺序：
- 为了保证填写当前状态的时候前面状态已经存到容器中，这样才能进行计算。
- 一般是从左向右/从上到下。
- 返回值：
- 通过最终得到的 dp 表和题意找到 dp 表中的结果。
提示：状态表示通常为'以 i 位置结尾/开头'。初始化通常通过第一个状态进行分析。做类似数字判断时，不要使用字符来简单的判断，而是将数字字符根据位数转变为真正的数字然后再进行判断。适当的需要的情况下可以开辟空间来处理边界问题。
实战演练
1. 第 N 个泰波那契数
题目描述
题目分析与解法
回顾五大步骤：
- 状态表示：
dp[i]表示第 i 个泰波那契数。 - 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。 - 初始化：需要前三个位置初始化，才能进行正常的开始。
- 填表顺序：从左向右。
- 返回值：
dp[n]。
空间优化：当我们在填某个表，某个状态只需要前面的若干个状态时，就可以使用滚动数组进行优化。本题仅需要某个数的前 3 个即可，可以用 3 个变量 abc 来标明前 3 个数。
代码实现
class Solution {
public:
{
;
(n >= ) dp[] = ;
(n >= ) dp[] = ;
(n >= ) dp[] = ;
( i = ; i <= n; i++) {
dp[i] = dp[i - ] + dp[i - ] + dp[i - ];
}
dp[n];
}
{
a = , b = , c = ;
ret = ;
(n == ) ;
(n == || n == ) ;
( i = ; i <= n; i++) {
ret = a + b + c;
a = b;
b = c;
c = ret;
}
ret;
}
};
