LeetCode每日一题 2023.5.12-全球观点
写在前面
开个坑...要准备毕业找offer了，得刷刷题了。之前自己嗯刷感觉刷完就容易忘，所以写写记录加深一下印象。
代码方面会用Java，因为自己用的比较多。别的语言看懂思路和代码应该可以轻易写出来。
题目描述
2140题：给定一个二维数组questions，每个数组元素长度为2，questions[i] = [pointsi, brainpoweri]。对于每个题目questions[i]，如果答此题则获得pointsi， 但是接下来brainpoweri道题不能作答。返回能获得的最大分数
(资料图)
思路
挺简单的一道DP，和01背包问题很像，可以用类似的思路。
定义状态dp[i]为从第i道题开始作答能获得的最大分数，则结果需要返回dp[0]，即从第0题开始作答。
状态转移方程可以表示为dp[i] = max(dp[i+1], pointsi+dp[i+1+brainpoweri])，即作答此题则获得分数并跳转到1+brainpoweri题。注意：1. 跳转题要+1，因为是brainpoweri题后。2. 如果i+1+brainpoweri的值超过数组界限，则不用考虑，方程退化到dp[i] = max(dp[i+1], pointsi)。
初始状态除dp[n-1]外为0，dp[n-1]初始化为pointsn-1，因为只能答此题了。
代码
class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] dp = new long[n];
dp[n-1] = questions[n-1][0];
for (int i = n-2; i >= 0; i--){
int[] cur = questions[i];
if (cur[1] + 1 + i <= n-1){
dp[i] = Math.max(dp[i+1], cur[0] + dp[i+1+cur[1]]);
}
else
dp[i] = Math.max(dp[i+1], cur[0]);
}
return dp[0];
}
}
结果
嗯，差不多就行了，不用优化
关键词：
相关阅读
- 06-14
最近更新
- 06-14
- 06-14
- 06-14
- 06-14
营业执照公示信息