1.买卖股票的最好时机一假设某股票每一天的价格存在数组prices你只能选择某一天买入之后某一天卖出求能获取的最大利润不能获利则利润为 0。限制不能先卖后买最多交易一次示例plaintext输入[7,1,5,6,4] 输出5 解释第2天价格1买入第4天价格6卖出6-15 输入[7,6,4,3,1] 输出0思路一次遍历维护变量min_price遍历到当前为止的最低股价维护max_profit当前最大收益每一天尝试用当天价格卖出profit prices[i] - min_price更新最大利润更新最低股价C AC 代码牛客标准cpp运行#include vector #include algorithm using namespace std; class Solution { public: int maxProfit(vectorint prices) { if (prices.empty()) return 0; int min_price prices[0]; int max_profit 0; for (int i 1; i prices.size(); i) { max_profit max(max_profit, prices[i] - min_price); min_price min(min_price, prices[i]); } return max_profit; } };复杂度时间\(O(n)\) 仅一次遍历空间\(O(1)\) 常数额外空间易错点不要双重暴力循环 \(O(n^2)\)大数据会超时利润不能为负数如果全程下跌直接返回 0更新顺序先计算收益再更新最低价保证不能当天买卖2.过河卒题意棋盘上 A 点有一个过河卒需要走到目标 B 点。卒行走规则只能向右、向下走。 棋盘上有一个马马会封锁控制点卒不能走到马以及马能一步跳到的位置。 求从起点到终点的可行路径总数。输入n m x y终点坐标 \((n,m)\)马坐标 \((x,y)\) 约定起点 \((0,0)\)核心思路动态规划\(dp[i][j]\)从 \((0,0)\) 走到 \((i,j)\) 的路径数量状态转移\(dp[i][j] dp[i-1][j] dp[i][j-1]\) 只能从上边、左边走来 3. 边界 \(dp[0][0] 1\) 起点方案为 1 第一行只能从左边来 \(dp[0][j]dp[0][j-1]\) 第一列只能从上边来 \(dp[i][0]dp[i-1][0]\) 4. 标记马的位置 马 8 个控制点这些位置 \(dp0\)不可通行数据范围提示路径数很大要用long longint 会溢出马的 8 个偏移量plaintext{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}C 完整 AC 代码牛客可直接提交cpp运行#include iostream #include cstring using namespace std; typedef long long ll; const int MAXN 25; ll dp[MAXN][MAXN]; bool ban[MAXN][MAXN]; // 标记禁止走的点 // 马八个方向 int dx[] {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[] {-1, 1, -2, 2, -2, 2, -1, 1}; int main() { int n, m, x, y; cin n m x y; // 标记马所在位置 ban[x][y] true; // 标记马能跳到的8个点 for(int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if(nx 0 ny 0 nx n ny m) ban[nx][ny] true; } // 起点如果被封锁直接0 if(!ban[0][0]) dp[0][0] 1; for(int i 0; i n; i) { for(int j 0; j m; j) { if(ban[i][j]) { dp[i][j] 0; continue; } // 跳过起点已经初始化 if(i 0 j 0) continue; ll up 0, left 0; if(i 0) up dp[i-1][j]; if(j 0) left dp[i][j-1]; dp[i][j] up left; } } cout dp[n][m] endl; return 0; }易错重点必须 long long数值极易溢出int 直接 WA坐标范围坐标从0开始不要误当成 1判断控制点不要越界禁止点直接置 0不能参与路径累加卒只能向右、向下没有左上右下简单样例测试输入plaintext6 6 3 3输出6拓展思考不用二维数组可以滚动数组空间优化成一维 dp [m1]适合更大范围。3.游游的水果大礼包题意简述游游准备制作水果大礼包。 有两种水果苹果、香蕉。 礼包规则大礼包一共选择k 个水果苹果数量不能少于 a 个不能多于 b 个剩下位置放香蕉 求一共有多少种搭配方案。形式化 设选苹果 x 个则香蕉 \(k-x\) 个。 条件a≤x≤b,0≤k−x也就是a≤x≤min(b,k)同时x≥0,k−x≥0对于合法的每一个 x方案数 1只要确定苹果数量香蕉数量唯一确定 答案 合法 x 的个数。标准解题步骤下限La上限Rmin(b,k)同时苹果不能超过总水果数香蕉数量 k−x≥0 自动等价 x≤k若 L R不存在合法方案答案 0否则答案 R-L1样例演示例 \(k6,a2,b5\) \(L2,R\min(5,6)5\) 方案2,3,4,5 → \(5-214\) 种例 \(k3,a2,b4\) \(R\min(4,3)3\) \(L2\) 方案2,3 → 2 种例 \(k2,a3,b5\) \(L3R2\) → 答案 0C AC 代码cpp运行#include iostream #include algorithm using namespace std; int main() { int k, a, b; cin k a b; int L a; int R min(b, k); int ans 0; if (L R) ans R - L 1; cout ans endl; return 0; }拓展如果你看到的是【可重组合版本】变种⚠️ 有另一道同名改编题 苹果至少 a香蕉至少 b一共选 k 个水果苹果 香蕉求方案。 条件x≥a,k−x≥b⇒x∈[a,k−b]依旧求区间内整数数量。谢谢
1.买卖股票的最好时机一假设某股票每一天的价格存在数组prices你只能选择某一天买入之后某一天卖出求能获取的最大利润不能获利则利润为 0。限制不能先卖后买最多交易一次示例plaintext输入[7,1,5,6,4] 输出5 解释第2天价格1买入第4天价格6卖出6-15 输入[7,6,4,3,1] 输出0思路一次遍历维护变量min_price遍历到当前为止的最低股价维护max_profit当前最大收益每一天尝试用当天价格卖出profit prices[i] - min_price更新最大利润更新最低股价C AC 代码牛客标准cpp运行#include vector #include algorithm using namespace std; class Solution { public: int maxProfit(vectorint prices) { if (prices.empty()) return 0; int min_price prices[0]; int max_profit 0; for (int i 1; i prices.size(); i) { max_profit max(max_profit, prices[i] - min_price); min_price min(min_price, prices[i]); } return max_profit; } };复杂度时间\(O(n)\) 仅一次遍历空间\(O(1)\) 常数额外空间易错点不要双重暴力循环 \(O(n^2)\)大数据会超时利润不能为负数如果全程下跌直接返回 0更新顺序先计算收益再更新最低价保证不能当天买卖2.过河卒题意棋盘上 A 点有一个过河卒需要走到目标 B 点。卒行走规则只能向右、向下走。 棋盘上有一个马马会封锁控制点卒不能走到马以及马能一步跳到的位置。 求从起点到终点的可行路径总数。输入n m x y终点坐标 \((n,m)\)马坐标 \((x,y)\) 约定起点 \((0,0)\)核心思路动态规划\(dp[i][j]\)从 \((0,0)\) 走到 \((i,j)\) 的路径数量状态转移\(dp[i][j] dp[i-1][j] dp[i][j-1]\) 只能从上边、左边走来 3. 边界 \(dp[0][0] 1\) 起点方案为 1 第一行只能从左边来 \(dp[0][j]dp[0][j-1]\) 第一列只能从上边来 \(dp[i][0]dp[i-1][0]\) 4. 标记马的位置 马 8 个控制点这些位置 \(dp0\)不可通行数据范围提示路径数很大要用long longint 会溢出马的 8 个偏移量plaintext{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}C 完整 AC 代码牛客可直接提交cpp运行#include iostream #include cstring using namespace std; typedef long long ll; const int MAXN 25; ll dp[MAXN][MAXN]; bool ban[MAXN][MAXN]; // 标记禁止走的点 // 马八个方向 int dx[] {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[] {-1, 1, -2, 2, -2, 2, -1, 1}; int main() { int n, m, x, y; cin n m x y; // 标记马所在位置 ban[x][y] true; // 标记马能跳到的8个点 for(int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if(nx 0 ny 0 nx n ny m) ban[nx][ny] true; } // 起点如果被封锁直接0 if(!ban[0][0]) dp[0][0] 1; for(int i 0; i n; i) { for(int j 0; j m; j) { if(ban[i][j]) { dp[i][j] 0; continue; } // 跳过起点已经初始化 if(i 0 j 0) continue; ll up 0, left 0; if(i 0) up dp[i-1][j]; if(j 0) left dp[i][j-1]; dp[i][j] up left; } } cout dp[n][m] endl; return 0; }易错重点必须 long long数值极易溢出int 直接 WA坐标范围坐标从0开始不要误当成 1判断控制点不要越界禁止点直接置 0不能参与路径累加卒只能向右、向下没有左上右下简单样例测试输入plaintext6 6 3 3输出6拓展思考不用二维数组可以滚动数组空间优化成一维 dp [m1]适合更大范围。3.游游的水果大礼包题意简述游游准备制作水果大礼包。 有两种水果苹果、香蕉。 礼包规则大礼包一共选择k 个水果苹果数量不能少于 a 个不能多于 b 个剩下位置放香蕉 求一共有多少种搭配方案。形式化 设选苹果 x 个则香蕉 \(k-x\) 个。 条件a≤x≤b,0≤k−x也就是a≤x≤min(b,k)同时x≥0,k−x≥0对于合法的每一个 x方案数 1只要确定苹果数量香蕉数量唯一确定 答案 合法 x 的个数。标准解题步骤下限La上限Rmin(b,k)同时苹果不能超过总水果数香蕉数量 k−x≥0 自动等价 x≤k若 L R不存在合法方案答案 0否则答案 R-L1样例演示例 \(k6,a2,b5\) \(L2,R\min(5,6)5\) 方案2,3,4,5 → \(5-214\) 种例 \(k3,a2,b4\) \(R\min(4,3)3\) \(L2\) 方案2,3 → 2 种例 \(k2,a3,b5\) \(L3R2\) → 答案 0C AC 代码cpp运行#include iostream #include algorithm using namespace std; int main() { int k, a, b; cin k a b; int L a; int R min(b, k); int ans 0; if (L R) ans R - L 1; cout ans endl; return 0; }拓展如果你看到的是【可重组合版本】变种⚠️ 有另一道同名改编题 苹果至少 a香蕉至少 b一共选 k 个水果苹果 香蕉求方案。 条件x≥a,k−x≥b⇒x∈[a,k−b]依旧求区间内整数数量。谢谢
