杨校老师课堂之基于C++的动态规划进行解题_信息学奥数赛-基础练习题

#include <iostream>
using namespace std;

int main() {
    // 定义变量n，用于接收输入的年份数
    int n;
    // 使用while循环，持续读取输入的n，只要输入不为0就继续循环
    while (cin >> n && n!= 0) {
        // 定义动态规划数组dp，用于存储每年的母牛数量，数组大小设为55，可根据需要调整
        int dp[55] = {0};
        // 设定边界条件：第1年年初，母牛的数量是1，所以dp[1]为1
        dp[1] = 1;
        // 设定边界条件：第2年年初，原来的1头母牛生了1头小牛，母牛总数变为2，所以dp[2]为2
        dp[2] = 2;
        // 设定边界条件：第3年年初，原来的母牛和第1年出生的小牛各生了1头小牛，母牛总数变为3，所以dp[3]为3
        dp[3] = 3;
        // 从第4年开始，利用状态转移方程计算每年的母牛数量
        for (int i = 4; i <= n; i++) {
            // 状态转移方程：第i年的母牛数量等于第i - 1年的母牛数量（上年存活的母牛）
            // 加上第i - 3年的母牛数量（因为3年前出生的小牛到今年开始可以生小牛了）
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        // 输出第n年的母牛数量
        cout << dp[n] << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;

// 定义一个常量MOD，用于取模运算，防止结果数值过大
int MOD = 100007;  

int main() {
    int n;
    // 从标准输入读取需要铺满的走道长度n（以2×n的形式理解）
    cin >> n;  
    // 定义动态规划数组dp，用于存储铺满2×i走道的不同方式数
    int dp[n + 1];  
    // 初始化边界条件：dp[0]表示铺满2×0的走道的方式数，有一种方式，即什么都不铺
    dp[0] = 1;  
    // 初始化边界条件：dp[1]表示铺满2×1的走道的方式数，有一种方式，即竖着放一块1×2的砖
    dp[1] = 1;  

    // 动态规划递推过程，从i = 2开始，逐步计算到i = n
    for (int i = 2; i <= n; i++) {  
        // 根据状态转移方程计算dp[i]：
        // dp[i]取决于两种情况：
        // 1. 最后一块砖竖着放（对应dp[i - 1]种铺法）
        // 2. 最后放一个2×2的单元（有两种等效方式，对应2 * dp[i - 2]种铺法）
        // 为防止数值过大，每次计算结果都对MOD取模
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % MOD;  
    }
    // 输出铺满2×n走道的不同方式数
    cout << dp[n] << endl;  
    return 0;
}```

---