本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程股票买卖【题目描述】给定一支股票接下来n nn天的价格设计一个算法计算出最大的利润。每天你可以进行买入或者卖出或者不进行任何操作但是需要遵守以下条件你不能同时参与多笔交易你必须在再次买入前卖出之前的股票。卖出股票后你无法在第二天买入股票即冷冻期为1 11天。【输入】第一行一个整数n ( 1 ≤ n ≤ 10 5 ) n(1≤n≤10^5)n(1≤n≤105)表示一共有n nn天。第二行一共有n nn个整数a i ( 1 ≤ a i ≤ 10 9 ) a_i(1≤a_i≤10^9)ai​(1≤ai​≤109)表示第i ii天的价格。【输出】输出一行包含一个整数表示最大的利润。【输入样例】5 2 3 4 1 3【输出样例】3【核心思想】问题分析给定n nn天的股票价格a i a_iai​每天可以买入、卖出或不操作但不能同时持有多只股票再次买入前必须卖出且卖出后有1 11天冷冻期第二天不能买入。求最大利润。这是一个状态机 DP问题需要设计多个状态表示不同的持仓和冷冻情况。算法选择状态机 DP线性 DP定义多个状态表示不同的交易状态状态设计状态0 00手中没有股票且不在冷冻期可以买入状态1 11手中持有股票状态2 22手中没有股票但处于冷冻期刚卖出不能买入关键步骤初始化d p [ 0 ] [ 0 ] 0 dp[0][0] 0dp[0][0]0第0 00天没有股票利润为0 00其他状态初始化为负无穷状态转移d p [ i ] [ 0 ] max ⁡ ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 2 ] ) dp[i][0] \max(dp[i-1][0], dp[i-1][2])dp[i][0]max(dp[i−1][0],dp[i−1][2])状态0 00可以从状态0 00不操作或从状态2 22冷冻期结束转移d p [ i ] [ 1 ] max ⁡ ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − a [ i ] ) dp[i][1] \max(dp[i-1][1], dp[i-1][0] - a[i])dp[i][1]max(dp[i−1][1],dp[i−1][0]−a[i])状态1 11可以从状态1 11继续持有或从状态0 00买入花费a [ i ] a[i]a[i]d p [ i ] [ 2 ] d p [ i − 1 ] [ 1 ] a [ i ] dp[i][2] dp[i-1][1] a[i]dp[i][2]dp[i−1][1]a[i]状态2 22只能从状态1 11卖出股票转移获得a [ i ] a[i]a[i]答案max ⁡ ( d p [ n ] [ 0 ] , d p [ n ] [ 2 ] ) \max(dp[n][0], dp[n][2])max(dp[n][0],dp[n][2])最后不能持有股票时间/空间复杂度时间复杂度O ( n ) O(n)O(n)一次遍历完成状态转移空间复杂度O ( n ) O(n)O(n)DP 数组存储可优化至O ( 1 ) O(1)O(1)状态机 DP 的核心思想状态设计根据题目约束设计合理的状态本题用三个状态表示持仓和冷冻情况状态转移明确每个状态可以从哪些状态转移而来确保状态转移的完备性最优子结构当前最优解由子问题的最优解组合而成空间优化由于只依赖前一天的状态可以用滚动数组优化至O ( 1 ) O(1)O(1)适用于有复杂约束的序列决策问题如股票交易、任务调度等【算法标签】#线性DP-一维【代码详解】#includeiostream#includecstring#includealgorithmusingnamespacestd;#defineintlonglongconstintN1e55;intn,a[N],dp[N][5];// dp[i][j]: 前i天状态j的最大收益signedmain(){cinn;for(inti1;in;i){cina[i];// 第i天的股价}memset(dp,-0x3f,sizeof(dp));// 初始化为负无穷dp[0][0]0;// 第0天没有股票for(inti1;in;i){// 状态0: 没有股票不操作dp[i][0]max(dp[i-1][0],dp[i-1][2]);// 状态1: 持有股票dp[i][1]max(dp[i-1][1],dp[i-1][0]-a[i]);// 状态2: 卖出股票后的冷冻期dp[i][2]dp[i-1][1]a[i];}coutmax(dp[n][0],dp[n][2]);// 最后不能持有股票return0;}【运行结果】5 2 3 4 1 3 3