- Reference
- Complexity
- DP问题的复杂度需要具体情况具体分析，粗略来说复杂度取决于状态转移方程，例题的时间复杂度为：\mathcal{O(N)}
P2437 蜜蜂路线 - 洛谷 | 计算机科学教育新生态
| DP五部曲 | 👇🏻对于此题 |
|---|
确定 dp[i] 含义 | | 第 i 个 fib() 数值为 dp[i] |
| 递推公式 | | dp_n = dp_{n-1} + dp_{n-2} |
dp[] 如何初始化 | | dp_0 = 1 \quad dp_1 = 1 |
| 遍历顺序 | | 从前向后 |
打印 dp[] | DEBUG | |
Template Code (对于 DP 来说，模版没什么用，重点还是看上面的五部曲)
C++
对于通过此题，还需要高精度，但本文讲动态规划，所以不涉及那部分内容，通过两个测试点即可
//build: g++ P1605.cpp -std=c++20 -o P1605
#include <iostream>
#include <vector>
void solve();
int main(){
solve();
return 0;
}
void solve() {
int m, n;
std::cin >> m >> n;
n = n - m;
// std::vector<BigInt> dp(n + 1);
std::vector<BigInt> dp(3);
dp[0] = 1; dp[1] = 1; // 由题目信息定义
for (int i = 2; i <= n; ++i) { // 这里 fib 从 0 开始，所以求到 n --- f(0) = 1, f(1) = 1
// 开 n 长 vector 的做法
// dp[i] = dp[i - 1] + dp[i - 2];
// dp[i - 2] = dp[i - 1];
// dp[i - 1] = dp[i];
// 三个变量的做法
dp[2] = dp[1] + dp[0];
dp[0] = dp[1];
dp[1] = dp[2];
}
std::cout << dp[2] << std::endl;
}