题目 石板问题 石板问题(通用跳跃版) 机器人走路 股票投资决策问题 知识闯关大冒险 最小花费爬楼梯 三角形路径挑战
石板问题
题目大意
你站在第 1 块石板上,每次可以走 1 块或 2 块石板,问你有多少种方法恰好走到第 nnn 块石板上。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 起点固定在第 1 块石板;
* 目标是第 nnn 块石板;
* 每步可以跳 1 或 2 格;
* 问一共有多少种合法路径能走到第 nnn 块石板。
这实际上是一个变形的 爬楼梯问题,标准动态规划模型。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路(动态规划)
状态设计
设 f[i]f[i]f[i] 表示恰好走到第 iii 块石板的方案数。
状态转移方程
因为每一步可以从 i−1i-1i−1 或 i−2i-2i−2 跳到 iii,所以有:
f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]f[i]=f[i−1]+f[i−2]
初始条件
* f[1]=1f[1] = 1f[1]=1:站在第 1 块,就是 1 种方案。
* f[2]=1f[2] = 1f[2]=1:从 1 → 2,也只有一种方法。
答案
输出 f[n]f[n]f[n] 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 状态数:O(n)O(n)O(n) 个状态;
* 每个状态转移耗时 O(1)O(1)O(1);
* 整体时间复杂度为 O(n)O(n)O(n);
* 空间复杂度也是 O(n)O(n)O(n),若用滚动数组可降至 O(1)O(1)O(1)(但这不是本题重点)。
数据范围 n≤45n \le 45n≤45,故该解法非常高效。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
石板问题(通用跳跃版)
题目大意
你站在第 1 块石板上,每一步可以跨越 111 到 kkk 块石板,问你一共有多少种方法可以恰好走到第 nnn 块石板上,答案对 114514114514114514 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个变种爬楼梯问题,允许步长为 111 到 kkk。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
设 f[i]f[i]f[i] 表示从第 1 块石板恰好走到第 iii 块石板的方案数。
则状态转移为:
f[i]=∑j=1kf[i−j]当 i−j≥1f[i] = \sum_{j=1}^{k} f[i-j] \quad \text{当 } i-j \geq 1f[i]=∑j=1k f[i−j]当 i−j≥1
注意:
* 初始时 f[1]=1f[1] = 1f[1]=1(从第1块出发,不动就是1种方式)
* 对于所有 iii,我们只从之前 kkk 步内的状态转移过来。
* 所有计算均取模 114514114514114514。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 外层循环 O(n)O(n)O(n);
* 内层最多循环 kkk 次;
* 整体时间复杂度:O(nk)O(nk)O(nk);
* 空间复杂度:O(n)O(n)O(n);
* 数据范围:1≤n≤105, 1≤k≤1001 \leq n \leq 10^5,\ 1 \leq k \leq 1001≤n≤105, 1≤k≤100,在时间限制内可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
机器人走路
题目大意
给一个 n×mn \times mn×m 的网格,机器人从左上角 (1,1)(1,1)(1,1) 出发,每次只能向右或下走一步,求走到右下角 (n,m)(n,m)(n,m) 的不同路径总数,答案对 114514114514114514 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个典型的动态规划(DP)路径计数问题。本质上是求从左上角走到右下角的组合数路径问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
状态表示:
令 dp[i][j]dp[i][j]dp[i][j] 表示从 (1,1)(1,1)(1,1) 走到 (i,j)(i,j)(i,j) 的路径总数。
状态转移:
每个位置 (i,j)(i,j)(i,j) 的路径数等于其上方和左方的路径数之和:
dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]
因为:
* 从 (i−1,j)(i-1,j)(i−1,j) 向下可以到 (i,j)(i,j)(i,j);
* 从 (i,j−1)(i,j-1)(i,j−1) 向右可以到 (i,j)(i,j)(i,j)。
边界条件:
* dp[1][1]=1dp[1][1] = 1dp[1][1]=1,表示起点的路径数为 1;
* 对于边界第一行和第一列,只能从一个方向走。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 状态数量:O(n⋅m)O(n \cdot m)O(n⋅m);
* 每个状态转移:O(1)O(1)O(1);
* 总时间复杂度:O(n⋅m)O(n \cdot m)O(n⋅m);
* 空间复杂度:O(n⋅m)O(n \cdot m)O(n⋅m);
* 在 n,m≤1000n, m \leq 1000n,m≤1000 的情况下,可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
股票投资决策问题
题目大意
给定一个长度为 nnn 的整数数组 aaa,其中 aia_iai 表示第 iii 天股票价格的涨跌幅度(正数表示涨,负数表示跌)。你需要选择一个连续子数组,使得子数组的元素和最大。输出这个最大收益值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 可以看成一个一维数组求最大子段和的问题。
* 需要找一个连续区间 [l,r][l, r][l,r],使得 ∑i=lrai\sum_{i=l}^{r} a_i∑i=lr ai 最大。
* 即便所有数都是负数,也要选择一个最小的负数(至少要选一天)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
状态表示:
* 令 dp[i]dp[i]dp[i] 表示以第 iii 天为结尾的连续区间的最大收益。
状态转移:
* dp[i]=max(dp[i−1]+a[i], a[i])dp[i] = \max(dp[i-1] + a[i],\ a[i])dp[i]=max(dp[i−1]+a[i], a[i])
意思是:要么接上前面的最大段(继续累计),要么重新开始从第 iii 天开始。
初始值:
* dp[1]=a[1]dp[1] = a[1]dp[1]=a[1],因为第一个数只能自己成段。
最终答案:
* 所有 dp[i]dp[i]dp[i] 中的最大值,即 max(dp[1∼n])\max(dp[1 \sim n])max(dp[1∼n])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 时间复杂度:O(n)O(n)O(n),只需遍历一次数组;
* 空间复杂度:O(n)O(n)O(n),但可进一步优化为 O(1)O(1)O(1)(只记录上一个状态和答案);
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
知识闯关大冒险
题目大意
给出一个整数数组 aaa,其中 aia_iai 表示第 iii 个关卡可以获得的知识点数。你最多可以选取一些不相邻的关卡,使得获得的知识点总和最大。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 不能选相邻关卡,意味着如果选了第 iii 个关卡,就不能选 i−1i-1i−1。
* 本质是一个子序列选择问题,但有相邻元素限制。
* 动态规划是最自然的思路。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
定义状态:
* dp[i]dp[i]dp[i] 表示前 iii 个关卡中,在不挑战相邻关卡的前提下最多可以收集的知识点数量。
状态转移:
* 对于第 iii 关,有两种情况:
1. 不选第 iii 个:那最多是 dp[i−1]dp[i-1]dp[i−1]
2. 选第 iii 个:那第 i−1i-1i−1 个不能选,总和为 dp[i−2]+a[i]dp[i-2] + a[i]dp[i−2]+a[i]
* 所以状态转移方程为:
dp[i]=max(dp[i−1], dp[i−2]+a[i])dp[i] = \max(dp[i-1],\ dp[i-2] + a[i])dp[i]=max(dp[i−1], dp[i−2]+a[i])
初始值:
* dp[1]=a[1]dp[1] = a[1]dp[1]=a[1]
* dp[2]=max(a[1],a[2])dp[2] = \max(a[1], a[2])dp[2]=max(a[1],a[2])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 时间复杂度:O(n)O(n)O(n),一次遍历计算所有状态;
* 空间复杂度:O(n)O(n)O(n),如果使用数组存储全部状态;可以优化成 O(1)O(1)O(1) 空间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最小花费爬楼梯
题目大意
给定一个长度为 nnn 的数组 aaa,其中 aia_iai 表示踩在第 iii 个台阶上的花费。你从第 000 层出发,每次可以跳一阶或两阶,问最小花费爬到第 nnn 层(楼顶,不用支付代价)是多少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 台阶编号为 0∼n−10 \sim n-10∼n−1;
* 终点是第 nnn 层,不需要付费;
* 起点可以从第 0 或第 1 个台阶起跳;
* 每次只能跳 1 或 2 阶;
* 最后一步可以从 n−1n-1n−1 或 n−2n-2n−2 跳到楼顶。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
令 dp[i] 表示跳到第 iii 个台阶所需的最小花费,则:
* 初始状态:
dp[0]=a[0],dp[1]=a[1]dp[0] = a[0],\quad dp[1] = a[1]dp[0]=a[0],dp[1]=a[1]
* 状态转移方程:
dp[i]=min(dp[i−1], dp[i−2])+a[i]dp[i] = \min(dp[i-1],\ dp[i-2]) + a[i]dp[i]=min(dp[i−1], dp[i−2])+a[i]
* 注意:我们的目标是跳到“第 n 层(楼顶)”,不需要再支付费用,因此最终结果是:
min(dp[n−1], dp[n−2])\min(dp[n-1],\ dp[n-2])min(dp[n−1], dp[n−2])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 时间复杂度:O(n)O(n)O(n)
* 空间复杂度:O(n)O(n)O(n)(可优化到 O(1)O(1)O(1))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三角形路径挑战
题目大意
给你一个数字三角形,从顶端出发,每一步只能向下一行的相邻两个位置之一走,问从顶到底的最小路径和是多少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 本质是一个有结构限制的路径最优化问题。
* 如果当前在第 iii 行第 jjj 个位置,则下一步只能走到第 i+1i+1i+1 行的第 jjj 或第 j+1j+1j+1 个位置。
* 求从顶部到底部的路径总和最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用动态规划(DP),核心思想是自顶向下或自底向上进行状态转移。
令 dp[i][j] 表示从顶端走到第 iii 行第 jjj 个位置的最小路径和。
* 状态转移方程:
dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+a[i][j]dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1]) + a[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] 时全部赋值为一个很大值(如 10910^9109),然后只在合法下标内转移。
* 最终答案:
* 是最底层的所有 dp[n][i] 中的最小值,即:
min(dp[n][1],dp[n][2],...,dp[n][n])\min(dp[n][1], dp[n][2], ..., dp[n][n])min(dp[n][1],dp[n][2],...,dp[n][n])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 状态数:每层 iii 有 iii 个元素,总状态数为 O(n2)O(n^2)O(n2);
* 每个状态计算复杂度为 O(1)O(1)O(1);
* 总时间复杂度为 O(n2)O(n^2)O(n2),可接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示