题目 机器人走路 2 最小路径和 古神肥波特 最大开销子字符串 知识闯关大冒险 II 石板问题（中等版）
机器人走路 2
题目大意
一个机器人位于一个 n×mn \times mn×m 的网格左上角，只能向下或向右移动一步，终点为右下角。
网格中有障碍物，不能经过。
现在给定地图，求从起点 (1,1)(1, 1)(1,1) 到终点 (n,m)(n, m)(n,m) 的不同路径数，结果对 114514114514114514 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是一个经典的带障碍物的动态规划路径计数问题。
设地图为 ai,ja_{i,j}ai,j ，其中：
* ai,j=0a_{i,j} = 0ai,j =0 表示可以走；
* ai,j=1a_{i,j} = 1ai,j =1 表示障碍，不能走。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
一、状态设计
令 dp[i][j]dp[i][j]dp[i][j] 表示从起点 (1,1)(1, 1)(1,1) 到达位置 (i,j)(i, j)(i,j) 的路径条数。
二、状态转移方程
若当前位置 ai,j=1a_{i,j} = 1ai,j =1（是障碍），则 dp[i][j]=0dp[i][j] = 0dp[i][j]=0；
否则可以由上方或左方走来：
dp[i][j]={0,如果 a[i][j]=1dp[i−1][j]+dp[i][j−1],否则dp[i][j] = \begin{cases} 0, & \text{如果 } a[i][j] = 1 \\ dp[i-1][j] + dp[i][j-1], & \text{否则} \end{cases}dp[i][j]={0,dp[i−1][j]+dp[i][j−1], 如果 a[i][j]=1否则
注意对 114514114514114514 取模。
三、初始状态
起点 (1,1)(1, 1)(1,1) 若为可通位置，则 dp[1][1]=1dp[1][1] = 1dp[1][1]=1；
其余位置可用上述转移公式逐行填充。
四、最终答案
输出 dp[n][m]dp[n][m]dp[n][m]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 状态数为 n×mn \times mn×m；
* 每个状态转移 O(1)O(1)O(1)；
总时间复杂度为 O(n×m)\boxed{O(n \times m)}O(n×m) 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++代码实现
最小路径和
题目大意
在一个 n×mn \times mn×m 的网格中，每个格子包含一个非负整数 ai,ja_{i,j}ai,j ，表示从该格子经过的代价。
机器人从左上角 (1,1)(1,1)(1,1) 出发，每次只能向右或下走一步，目标是走到右下角 (n,m)(n,m)(n,m)。请你求出一条代价最小的路径，输出其总代价。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 状态受限于只能向右或向下；
* 每个位置只能从左边或上边转移来；
* 是典型的 二维动态规划路径代价最小值问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
一、状态定义
令 dp[i][j]dp[i][j]dp[i][j] 表示走到第 iii 行第 jjj 列的最小路径和。
二、状态转移方程
从左或上转移而来：
dp[i][j]=min(dp[i−1][j], dp[i][j−1])+a[i][j]dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j]dp[i][j]=min(dp[i−1][j], dp[i][j−1])+a[i][j]
三、边界初始化
* dp[1][1]=a[1][1]dp[1][1] = a[1][1]dp[1][1]=a[1][1]；
* 第一行只能从左走来：dp[1][j]=dp[1][j−1]+a[1][j]dp[1][j] = dp[1][j-1] + a[1][j]dp[1][j]=dp[1][j−1]+a[1][j]；
* 第一列只能从上走来：dp[i][1]=dp[i−1][1]+a[i][1]dp[i][1] = dp[i-1][1] + a[i][1]dp[i][1]=dp[i−1][1]+a[i][1]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 状态数为 n×mn \times mn×m；
* 每个状态转移 O(1)O(1)O(1)；
因此总时间复杂度为 O(n×m)\boxed{O(n \times m)}O(n×m) ，空间复杂度为 O(n×m)O(n \times m)O(n×m)（可优化为 O(m)O(m)O(m)）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现（C++）
古神肥波特
题目大意
给定一个长度为 nnn 的股票价格数组 aaa，其中 aia_iai 表示第 iii 天的股价。你只能进行一次买入和一次卖出操作（卖出必须发生在买入之后），求最大可能利润。
如果无论何时买入卖出都无法盈利，输出 000。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一道典型的单次股票买卖最大利润问题。
我们希望找出一段时间 [i,j][i, j][i,j]，使得 i<ji < ji<j 且 aj−aia_j - a_iaj −ai 最大，答案即为该最大值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
我们遍历价格数组，同时维护当前最低买入价，并在每一天尝试计算“若今天卖出，利润是多少”。
一、变量定义
* minPriceminPriceminPrice：到当前为止的最小股价（买入价）；
* ansansans：最大利润。
二、状态转移逻辑
遍历 i=1i = 1i=1 到 nnn：
* 更新最低买入价：
minPrice=min(minPrice,a[i])minPrice = \min(minPrice, a[i])minPrice=min(minPrice,a[i])
* 当前卖出能得到的利润：
profit=a[i]−minPriceprofit = a[i] - minPriceprofit=a[i]−minPrice
* 更新最大利润：
ans=max(ans,profit)ans = \max(ans, profit)ans=max(ans,profit)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 仅需一次遍历数组；
* 每步操作均为 O(1)O(1)O(1)；
总时间复杂度为 O(n)\boxed{O(n)}O(n) ，空间复杂度为 O(1)\boxed{O(1)}O(1) 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码实现
最大开销子字符串
题目大意
给定：
* 一个字符串 sss（仅含小写字母）；
* 一个字符集 charscharschars，每个字符对应一个自定义价值 valsvalsvals；
* 字符在 charscharschars 中时价值为 vals[i]vals[i]vals[i]，否则为其字母序（如 'a' = 1，'b' = 2，…）；
* 定义某一子串的开销为其中每个字符的价值之和；
* 要求在所有连续子串中找出最大开销。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 要对 sss 中每个字符确定其价值；
* 然后问题转化为：求一个数组中的 最大连续子数组和（即经典的 最大子段和问题）；
* 可使用动态规划求解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
一、预处理价值映射
* 用一个 int val[26] 数组，初始化为 'a' 到 'z' 的字母序；
* 然后根据输入将 chars[i]chars[i]chars[i] 对应的值覆盖进去；
* 最终我们可以 O(1)O(1)O(1) 得到任意字符的价值。
二、转换成数值数组 + 最大子段和
将字符串 sss 映射为整数数组 vvv，每个元素为对应字符的价值。
设 dpidp_idpi 为以第 iii 个字符结尾的最大开销：
dpi=max(dpi−1+vi, vi)dp_i = \max(dp_{i-1} + v_i, \ v_i)dpi =max(dpi−1 +vi , vi )
更新最大值：ans=max(ans,dpi)ans = \max(ans, dp_i)ans=max(ans,dpi )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 预处理价值表：O(m)O(m)O(m)；
* 映射整个字符串为价值数组：O(n)O(n)O(n)；
* 最大子段和扫描：O(n)O(n)O(n)；
总时间复杂度为 O(n)\boxed{O(n)}O(n) ，适用于 n≤105n \le 10^5n≤105 的数据范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码实现
知识闯关大冒险 II
题目大意
有 nnn 个围成一个环的关卡，每个关卡含有 aia_iai 个知识点。你要从中选出若干个关卡来挑战，收集尽可能多的知识点，但有以下限制：
* 不能挑战相邻的两个关卡；
* 第一个和最后一个关卡也被认为是相邻的。
求你最多能收集的知识点总数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
与一维数组版本相比，它加了一个“首尾相邻”的限制。
由于不能同时选第一个和最后一个元素，我们可以将环“断开”，分成两个线性子问题求解：
* 方案一：选择第一个，不能选最后一个 ⇒ 在 a[1∼n−1]a[1 \sim n-1]a[1∼n−1] 上做非环形最大不连续子序列和；
* 方案二：不选第一个，可以选最后一个 ⇒ 在 a[2∼n]a[2 \sim n]a[2∼n] 上做同样处理；
最终答案为两者中的最大值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
状态定义
设 dp[i]dp[i]dp[i] 表示在第 iii 个关卡结束时，能收集到的最大知识点数。
状态转移方程
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])
表示当前关卡要么不选（延续上一状态），要么选（加上 i−2i-2i−2 的最优值 + 当前值）。
边界条件
* 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)\boxed{O(n)}O(n) ；
* 空间优化后空间复杂度为 O(1)O(1)O(1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码实现
石板问题（中等版）
题目大意
你站在第 111 块石板上，每次可以选择跨 111、222 或 333 块石板。
问有多少种方法恰好到达第 nnn 块石板？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 起点为第 111 块石板；
* 每一步可跨 111、222 或 333 块；
* 求到达第 nnn 块石板的方案总数。
注意，题目要求 恰好 到达第 nnn 块石板，因此不能超过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
本题是斐波那契式动态规划的典型模型（可以跳 1、2、3 步）。
状态定义
* 令 dp[i]dp[i]dp[i] 表示到达第 iii 块石板的方案数。
状态转移方程
* 从第 i−1i-1i−1、i−2i-2i−2、i−3i-3i−3 块跳来：
dp[i]=dp[i−1]+dp[i−2]+dp[i−3]dp[i] = dp[i-1] + dp[i-2] + dp[i-3]dp[i]=dp[i−1]+dp[i−2]+dp[i−3]
边界条件
* dp[1]=1dp[1] = 1dp[1]=1：起点；
* dp[2]=1dp[2] = 1dp[2]=1：只能从 111 跳一步；
* dp[3]=2dp[3] = 2dp[3]=2：从 1→31 \to 31→3（跳 2 步），或 1→2→31 \to 2 \to 31→2→3（两次跳 1 步）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个 dp[i]dp[i]dp[i] 只依赖前 333 项；
* 整体复杂度为 O(n)\boxed{O(n)}O(n) ；
* 空间复杂度可优化为 O(1)O(1)O(1)（滚动变量形式）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++代码实现
