Beginners in dynamic programming

• Reference
  • Wiki
    • 动态规划部分简介 - OI Wiki
  • 基础
    • [[Fibonacci]]
  • 视频
    • 从此再也不怕动态规划了，动态规划解题方法论大曝光 ！| 理论基础 |力扣刷题总结| 动态规划入门 bilibili
    • 手把手带你入门动态规划 | LeetCode：509.斐波那契数 bilibili
  • 题目
    • P2437 蜜蜂路线 - 洛谷 | 计算机科学教育新生态
  • 进阶
    • 背包 DP - OI Wiki
  • 拓展
    • [[BigNum|高精度]]
  • 讨论
• 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;
}