有基础班_day02课上题目

zxcvbnm

2025-07-02 16:26:27

发布于：上海

14阅读

0回复

0点赞

题目
石板问题
石板问题（通用跳跃版）
机器人走路
股票投资决策问题
知识闯关大冒险
最小花费爬楼梯
三角形路径挑战

石板问题

题目大意

你站在第 1 块石板上，每次可以走 1 块或 2 块石板，问你有多少种方法恰好走到第 $n$ 块石板上。

题意分析

起点固定在第 1 块石板；
目标是第 $n$ 块石板；
每步可以跳 1 或 2 格；
问一共有多少种合法路径能走到第 $n$ 块石板。

这实际上是一个变形的 爬楼梯问题，标准动态规划模型。

解题思路（动态规划）

状态设计

设 $f[i]$ 表示恰好走到第 $i$ 块石板的方案数。

状态转移方程

因为每一步可以从 $i-1$ 或 $i-2$ 跳到 $i$ ，所以有：

$f[i] = f[i-1] + f[i-2]$

初始条件

$f[1] = 1$ ：站在第 1 块，就是 1 种方案。
$f[2] = 1$ ：从 1 → 2，也只有一种方法。

答案

输出 $f[n]$ 即可。

时间复杂度解析

状态数： $O(n)$ 个状态；
每个状态转移耗时 $O(1)$ ；
整体时间复杂度为 $O(n)$ ；
空间复杂度也是 $O(n)$ ，若用滚动数组可降至 $O(1)$ （但这不是本题重点）。

数据范围 $n \le 45$ ，故该解法非常高效。

代码演示

#include <iostream>
using namespace std;

int main() {
    long long f[50];  // f[i] 表示恰好走到第 i 块石板的方案数
    int n;
    cin >> n;

    f[1] = 1;  // 只有1块石板，原地不动就是一种方式
    f[2] = 1;  // 从1跳到2，只有一种方式

    for(int i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];  // 状态转移方程
    }

    cout << f[n];  // 输出到达第n块石板的总方案数
    return 0;
}

石板问题（通用跳跃版）

题目大意

你站在第 1 块石板上，每一步可以跨越 $1$ 到 $k$ 块石板，问你一共有多少种方法可以恰好走到第 $n$ 块石板上，答案对 $114514$ 取模。

题意分析

这是一个变种爬楼梯问题，允许步长为 $1$ 到 $k$ 。

解题思路

设 $f[i]$ 表示从第 1 块石板恰好走到第 $i$ 块石板的方案数。

则状态转移为：

$f[i] = \sum_{j=1}^{k} f[i-j] \quad \text{当 } i-j \geq 1$

注意：

初始时 $f[1] = 1$ （从第1块出发，不动就是1种方式）
对于所有 $i$ ，我们只从之前 $k$ 步内的状态转移过来。
所有计算均取模 $114514$ 。

时间复杂度分析

外层循环 $O(n)$ ；
内层最多循环 $k$ 次；
整体时间复杂度： $O(nk)$ ；
空间复杂度： $O(n)$ ；
数据范围： $1 \leq n \leq 10^5,\ 1 \leq k \leq 100$ ，在时间限制内可以通过。

代码演示

#include <iostream>
using namespace std;

const int MOD = 114514;
const int N = 1e5 + 10;

int f[N];

int main() {
    int n, k;
    cin >> n >> k;

    f[1] = 1; // 起点就在第1块石板上
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (i - j >= 1) {
                f[i] = (f[i] + f[i - j]) % MOD; // 累加来自前k个石板的路径数
            }
        }
    }

    cout << f[n] << endl; // 输出恰好走到第n块石板的方案数
    return 0;
}

机器人走路

题目大意

给一个 $n \times m$ 的网格，机器人从左上角 $(1,1)$ 出发，每次只能向右或下走一步，求走到右下角 $(n,m)$ 的不同路径总数，答案对 $114514$ 取模。

题意分析

这是一个典型的动态规划（DP）路径计数问题。本质上是求从左上角走到右下角的组合数路径问题。

解题思路

状态表示：

令 $dp[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 的路径总数。

状态转移：

每个位置 $(i,j)$ 的路径数等于其上方和左方的路径数之和：

$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

因为：

从 $(i-1,j)$ 向下可以到 $(i,j)$ ；
从 $(i,j-1)$ 向右可以到 $(i,j)$ 。

边界条件：

$dp[1][1] = 1$ ，表示起点的路径数为 1；
对于边界第一行和第一列，只能从一个方向走。

时间复杂度分析

状态数量： $O(n \cdot m)$ ；
每个状态转移： $O(1)$ ；
总时间复杂度： $O(n \cdot m)$ ；
空间复杂度： $O(n \cdot m)$ ；
在 $n, m \leq 1000$ 的情况下，可以通过。

代码演示

#include <iostream>
using namespace std;

const int MOD = 114514;
const int N = 1010;

int dp[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    dp[1][1] = 1; // 起点初始化

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(i == 1 && j == 1) continue; // 起点已初始化
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
        }
    }

    cout << dp[n][m] << endl; // 输出终点的路径数
    return 0;
}

股票投资决策问题

题目大意

给定一个长度为 $n$ 的整数数组 $a$ ，其中 $a_i$ 表示第 $i$ 天股票价格的涨跌幅度（正数表示涨，负数表示跌）。你需要选择一个连续子数组，使得子数组的元素和最大。输出这个最大收益值。

题意分析

可以看成一个一维数组求最大子段和的问题。
需要找一个连续区间 $[l, r]$ ，使得 $\sum_{i=l}^{r} a_i$ 最大。
即便所有数都是负数，也要选择一个最小的负数（至少要选一天）。

解题思路

状态表示：

令 $dp[i]$ 表示以第 $i$ 天为结尾的连续区间的最大收益。

状态转移：

$dp[i] = \max(dp[i-1] + a[i],\ a[i])$

意思是：要么接上前面的最大段（继续累计），要么重新开始从第 $i$ 天开始。

初始值：

$dp[1] = a[1]$ ，因为第一个数只能自己成段。

最终答案：

所有 $dp[i]$ 中的最大值，即 $\max(dp[1 \sim n])$

时间复杂度分析

时间复杂度： $O(n)$ ，只需遍历一次数组；
空间复杂度： $O(n)$ ，但可进一步优化为 $O(1)$ （只记录上一个状态和答案）；

代码演示

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], dp[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = a[1];       // 初始化最大收益
    dp[1] = a[1];         // 第一天单独成段

    for(int i = 2; i <= n; i++)
    {
        dp[i] = max(dp[i-1] + a[i], a[i]);  // 转移方程
        ans = max(ans, dp[i]);              // 更新答案
    }

    cout << ans << endl;
    return 0;
}

知识闯关大冒险

题目大意

给出一个整数数组 $a$ ，其中 $a_i$ 表示第 $i$ 个关卡可以获得的知识点数。你最多可以选取一些不相邻的关卡，使得获得的知识点总和最大。

题意分析

不能选相邻关卡，意味着如果选了第 $i$ 个关卡，就不能选 $i-1$ 。
本质是一个子序列选择问题，但有相邻元素限制。
动态规划是最自然的思路。

解题思路

定义状态：

$dp[i]$ 表示前 $i$ 个关卡中，在不挑战相邻关卡的前提下最多可以收集的知识点数量。

状态转移：

对于第 $i$ 关，有两种情况：
1. 不选第 $i$ 个：那最多是 $dp[i-1]$
2. 选第 $i$ 个：那第 $i-1$ 个不能选，总和为 $dp[i-2] + a[i]$
所以状态转移方程为：

$dp[i] = \max(dp[i-1],\ dp[i-2] + a[i])$

初始值：

$dp[1] = a[1]$
$dp[2] = \max(a[1], a[2])$

时间复杂度解析

时间复杂度： $O(n)$ ，一次遍历计算所有状态；
空间复杂度： $O(n)$ ，如果使用数组存储全部状态；可以优化成 $O(1)$ 空间。

代码演示

#include <iostream>
using namespace std;

const int N = 100010;
int dp[N], a[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    dp[1] = a[1];
    dp[2] = max(a[1], a[2]);

    for(int i = 3; i <= n; i++)
        dp[i] = max(dp[i-1], dp[i-2] + a[i]);

    cout << dp[n];
    return 0;
}

最小花费爬楼梯

题目大意

给定一个长度为 $n$ 的数组 $a$ ，其中 $a_i$ 表示踩在第 $i$ 个台阶上的花费。你从第 $0$ 层出发，每次可以跳一阶或两阶，问最小花费爬到第 $n$ 层（楼顶，不用支付代价）是多少。

题意分析

台阶编号为 $0 \sim n-1$ ；
终点是第 $n$ 层，不需要付费；
起点可以从第 0 或第 1 个台阶起跳；
每次只能跳 1 或 2 阶；
最后一步可以从 $n-1$ 或 $n-2$ 跳到楼顶。

解题思路

令 dp[i] 表示跳到第 $i$ 个台阶所需的最小花费，则：

初始状态：

$dp[0] = a[0],\quad dp[1] = a[1]$
状态转移方程：

$dp[i] = \min(dp[i-1],\ dp[i-2]) + a[i]$
注意：我们的目标是跳到“第 n 层（楼顶）”，不需要再支付费用，因此最终结果是：

$\min(dp[n-1],\ dp[n-2])$

时间复杂度分析

时间复杂度： $O(n)$
空间复杂度： $O(n)$ （可优化到 $O(1)$ ）

代码演示

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], dp[N];

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> a[i];

    dp[0] = a[0];
    dp[1] = a[1];

    for(int i = 2; i < n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + a[i];
    }

    cout << min(dp[n - 1], dp[n - 2]) << endl;
    return 0;
}

三角形路径挑战

题目大意

给你一个数字三角形，从顶端出发，每一步只能向下一行的相邻两个位置之一走，问从顶到底的最小路径和是多少。

题意分析

本质是一个有结构限制的路径最优化问题。
如果当前在第 $i$ 行第 $j$ 个位置，则下一步只能走到第 $i+1$ 行的第 $j$ 或第 $j+1$ 个位置。
求从顶部到底部的路径总和最小值。

解题思路

使用动态规划（DP），核心思想是自顶向下或自底向上进行状态转移。

令 dp[i][j] 表示从顶端走到第 $i$ 行第 $j$ 个位置的最小路径和。

状态转移方程：

$dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1]) + a[i][j]$
边界情况：
- dp[1][1] = a[1][1]
- 为防止访问越界，可以在初始化 dp[i][j] 时全部赋值为一个很大值（如 $10^9$ ），然后只在合法下标内转移。
最终答案：
- 是最底层的所有 dp[n][i] 中的最小值，即：
  
  $\min(dp[n][1], dp[n][2], ..., dp[n][n])$

时间复杂度分析

状态数：每层 $i$ 有 $i$ 个元素，总状态数为 $O(n^2)$ ；
每个状态计算复杂度为 $O(1)$ ；
总时间复杂度为 $O(n^2)$ ，可接受。

代码演示

#include <iostream>
using namespace std;

const int N = 1010;
int a[N][N], dp[N][N];

int main() {
    int n;
    cin >> n;

    // 输入三角形
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    // 初始化 dp 数组为较大值
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j] = 1e9;  // 无穷大，表示不可达
        }
    }

    dp[1][1] = a[1][1]; // 起点

    // 动态规划状态转移
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            // 从上一层的 j 或 j-1 转移
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
        }
    }

    // 答案是最后一层的最小值
    int ans = 1e9;
    for(int i = 1; i <= n; i++) {
        ans = min(ans, dp[n][i]);
    }

    cout << ans << endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

石板问题

题目大意

题意分析

解题思路（动态规划）

状态设计

状态转移方程

初始条件

答案

时间复杂度解析

代码演示

石板问题（通用跳跃版）

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

机器人走路

题目大意

题意分析

解题思路

状态表示：

状态转移：

边界条件：

时间复杂度分析

代码演示

股票投资决策问题

题目大意

题意分析

解题思路

状态表示：

状态转移：

初始值：

最终答案：

时间复杂度分析

代码演示

知识闯关大冒险

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

最小花费爬楼梯

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

三角形路径挑战

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

热门讨论