Leetcode 简单线性递推:正反两种方法
2022/1/17 6:06:29
本文主要是介绍Leetcode 简单线性递推:正反两种方法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
周赛差点翻车,LC 5982. Solving Questions With Brainpower
题意:有n个问题,只能依次解决,对于第i个问题,可以跳过,也可以选择解决,解决能获得questions[i][0]的分数,但是接下来的questions[i][1]个问题都不能做,求可以得到的最大分数。
方法:由于需要按顺序解决,所以排除排序+优先队列+贪心那一套;又不能是简单的贪心,因为某个问题是否选择解决,会影响后面可能得到的分数,所以很可能是个dp.
先看一种直观点的:从后往前dp
方法一:倒序DP(查表)
定义:dp[i]表示后i个问题可以得到的最大分数
对于dp[i],也就是对于第i个问题,
如果不选,dp[i] = dp[i-1],因为没有选,最大的分数就和前面的相同
如果选,dp[i] = max(dp[i], dp[i+questions[i][1]+1] + questions[i][0],因为接着的 questions[i][1] 个都不能选嘛
class Solution { public: long long mostPoints(vector<vector<int> >& questions) { long long ans = 0; int n = questions.size(); vector<long long>dp(n+1, 0); dp[n-1] = questions[n-1][0]; for(int i = n-2;i >= 0;i--) { if(i+questions[i][1] +1 < n) dp[i] = max(dp[i+1], dp[i+questions[i][1]+1] + questions[i][0]); else dp[i] = max(dp[i+1], (long long)questions[i][0]); } return dp[0]; } };
方法二:正向刷表
前面那种相当于递推,dp[i] 计算过程中要用到的值已经计算出来了,可以查表得到。
而正向是不断刷新dp数组,相当于计算每个问题的贡献。
参考 【解决智力问题】正向 DP
定义:dp[i]表示前i题的最大分数
选择跳过,不加此题得分,后续的题继承得分
选择做题,加上此题得分,跳过若干题后的下一题继承得分
class Solution { public: long long mostPoints(vector<vector<int>>& questions) { int n = questions.size(); vector<long long> dp(n, 0); for (int i = 0; i < n; i++) { int next = i + 1; if (next < n) dp[next] = max(dp[next], dp[i]); next = i + questions[i][1] + 1; dp[i] += questions[i][0]; // if (next < n) dp[next] = max(dp[next], dp[i]); } long long ans = *max_element(dp.begin(), dp.end()); // 取dp中的最大值 return ans; } };
这篇关于Leetcode 简单线性递推:正反两种方法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升