海口建站模板全国互联网公司排名

海口建站模板,全国互联网公司排名,吉林省干部网络培训学院官网,dedecms做的网站首页被挂马【LetMeFly】3573.买卖股票的最佳时机 V#xff1a;深度优先搜索 / 动态规划#xff1a;通俗讲解 力扣题目链接#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-v/ 给你一个整数数组 prices#xff0c;其中 prices[i] 是第 i 天股票的价格深度优先搜索 / 动态规划通俗讲解力扣题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-v/给你一个整数数组prices其中prices[i]是第i天股票的价格美元以及一个整数k。你最多可以进行k笔交易每笔交易可以是以下任一类型普通交易在第i天买入然后在之后的第j天卖出其中i j。你的利润是prices[j] - prices[i]。做空交易在第i天卖出然后在之后的第j天买回其中i j。你的利润是prices[i] - prices[j]。注意你必须在开始下一笔交易之前完成当前交易。此外你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。通过进行最多k笔交易返回你可以获得的最大总利润。示例 1:输入:prices [1,7,9,8,2], k 2输出:14解释:我们可以通过 2 笔交易获得 14 美元的利润一笔普通交易第 0 天以 1 美元买入第 2 天以 9 美元卖出。一笔做空交易第 3 天以 8 美元卖出第 4 天以 2 美元买回。示例 2:输入:prices [12,16,19,19,8,1,19,13,9], k 3输出:36解释:我们可以通过 3 笔交易获得 36 美元的利润一笔普通交易第 0 天以 12 美元买入第 2 天以 19 美元卖出。一笔做空交易第 3 天以 19 美元卖出第 4 天以 8 美元买回。一笔普通交易第 5 天以 1 美元买入第 6 天以 19 美元卖出。提示:2 prices.length 1031 prices[i] 1091 k prices.length / 2自我评价好文x1(bushi)解题方法一深度优先搜索定义dfs(i, j, status)含义为0到i ii天共进行了j jj次买入或做空操作status0代表第i ii天要到没持有股票状态1代表第i ii天要到手持股票的状态2代表第i ii天要到做空的状态假设买入或做空时立刻消耗交易次数(卖出或还上时交易完成不二次消耗次数)那么有如果status为0这天结束后两清可昨天本就两清今天什么都没干(dfs(i-1, j, 0))可昨天是手持股票状态今天卖了(dfs(i-1, j, 1) prices[i])可昨天是空头状态今天买回来补上了(dfs(i-1, j, 2) - prices[i])。如果status为1这天结束后手持股票可昨天本就持有股票今天什么都没干(dfs(i-1, j, 1))可昨天两清今天刚买入(dfs(i-1, j-1, 0) - prices[i])。如果status为2这天结束后欠还股票可昨天就是欠股票状态今天什么都没干(dfs(i-1, j, 2))可昨天两清今天做空提前卖了股票(dfs(i-1, j-1, 0) prices[i])。边界条件可用操作次数始终不能为负如果为负返回“负无穷”天数为-1时交易开始前只能处于两清状态如果交易开始前i − 1 i-1i−1状态已经处在持股或空头则说明状态不合法返回“负无穷”。时空复杂度时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)空间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)AC代码C/* * LastEditTime: 2025-12-17 23:09:09 */typedeflonglongll;classSolution{private:vectorintprices;unordered_mapint,llcache;inlineintgetKey(inti,intj,intstatus){returni*3000j*3status;}lldfs(inti,intj,intstatus){// 0~i天 最多交易j次// status: 0无1买2空头intkeygetKey(i,j,status);if(cache.count(key)){returncache[key];}if(j0){return-1000000000000000;}if(i0){returnstatus?-1000000000000000:0;}if(status0){returncache[key]max({dfs(i-1,j,0),dfs(i-1,j,1)prices[i],dfs(i-1,j,2)-prices[i]});}elseif(status1){returncache[key]max(dfs(i-1,j-1,0)-prices[i],dfs(i-1,j,1));}else{returncache[key]max(dfs(i-1,j-1,0)prices[i],dfs(i-1,j,2));}}public:llmaximumProfit(vectorintprices,intk){this-pricesmove(prices);returndfs(this-prices.size()-1,k,0);}};Pythonpython记得最终返回结果前强制清空下缓存虽然python也有gc机制但可能gc不及时导致MLE。 LastEditTime: 2025-12-17 23:18:54 fromtypingimportListfromfunctoolsimportcachefrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)-int:nlen(prices)cachedefdfs(i:int,j:int,status:int)-int:0无1有2空头ifj0:return-infifi0:return-infifstatuselse0ifstatus0:returnmax(dfs(i-1,j,0),dfs(i-1,j,1)prices[i],dfs(i-1,j,2)-prices[i])elifstatus1:returnmax(dfs(i-1,j,1),dfs(i-1,j-1,0)-prices[i])else:returnmax(dfs(i-1,j,2),dfs(i-1,j-1,0)prices[i])ansdfs(n-1,k,0)dfs.cache_clear()returnans解题方法二动态规划将深度优先搜索翻译成递推ifstatus0:returnmax(dfs(i-1,j,0),dfs(i-1,j,1)prices[i],dfs(i-1,j,2)-prices[i])elifstatus1:returnmax(dfs(i-1,j,1),dfs(i-1,j-1,0)-prices[i])else:returnmax(dfs(i-1,j,2),dfs(i-1,j-1,0)prices[i])翻译为dp[i][j][0]max(dp[i-1][j][0],dp[i-1][j][1]price,dp[i-1][j][2]-price)dp[i][j][1]max(dp[i-1][j][1],dp[i-1][j-1][0]-price)dp[i][j][2]max(dp[i-1][j][2],dp[i-1][j-1][0]price)注意为了防止下标出现-1可以令所有i在作dp下标时加上1dp[i1][j][0]max(dp[i][j][0],dp[i][j][1]price,dp[i][j][2]-price)dp[i1][j][1]max(dp[i][j][1],dp[i][j-1][0]-price)dp[i1][j][2]max(dp[i][j][2],dp[i][j-1][0]price)时空复杂度时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)空间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)AC代码Python LastEditTime: 2025-12-17 23:51:56 fromtypingimportListfrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)-int:nlen(prices)# dp[i][j][status]: i有效范围0~n-1j有效范围0~k这俩都多开一个无效状态的空间dp[[[-inf]*3for_inrange(k2)]for_inrange(n1)]forjinrange(1,k2):dp[0][j][0]0fori,priceinenumerate(prices):forjinrange(1,k2):dp[i1][j][0]max(dp[i][j][0],dp[i][j][1]price,dp[i][j][2]-price)dp[i1][j][1]max(dp[i][j][1],dp[i][j-1][0]-price)dp[i1][j][2]max(dp[i][j][2],dp[i][j-1][0]price)returndp[-1][-1][0]解题方法三动态规划空间优化不难发现第i ii天dp[i1][xx][x]数据仅和第i − 1 i-1i−1天有关dp[i][xx][x]因此可以优化掉数组第一维。注意j要倒序遍历因为j依赖的是上一天的j-1如果先更新j-1再更新j则会重复计算。时空复杂度时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)空间复杂度O ( k ) O(k)O(k)AC代码Python LastEditTime: 2025-12-17 23:58:31 fromtypingimportListfrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)-int:nlen(prices)# dp[i][j][status]: i有效范围0~n-1j有效范围0~k这俩都多开一个无效状态的空间dp[[-inf]*3for_inrange(k2)]forjinrange(1,k2):dp[j][0]0fori,priceinenumerate(prices):forjinrange(k1,0,-1):dp[j][0]max(dp[j][0],dp[j][1]price,dp[j][2]-price)dp[j][1]max(dp[j][1],dp[j-1][0]-price)dp[j][2]max(dp[j][2],dp[j-1][0]price)returndp[-1][0]同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源