首页

动规来力！！！

2140.解决智力问题

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。
    请你返回这场考试里你能获得的 最高分数。

提示：

  • 1 <= questions.length <= 105
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 105

解题思路

解决我的智力问题（不是🤯

看了题解发现是打家劫舍的变体题，所以带着一块儿做了。

👉相当于如果选了k，接下来有x个不能选：打家劫舍是x=1，本题x=questions[i][1]。

  1. 子问题
    原问题：“完成考试（即所有题都已解决or跳过）能获得的最大分数”→子问题：“完成前k道题能获得的最大分数”

  2. 递推关系
    👉已知子问题f(k)，那么只关注当前（即第k道）题，只有两种做题方法：
    做k && 做k+xor不做k && 做k+1

👉递推关系：f(k)=max{f(k-1),k-1道题的分数+f(k-1+x)}

边界：无题目（k=0）和只有一道题(k=1)

  1. dp数组的计算顺序
    ✅️dp[k]依赖于dp[k-1]和dp[k-1+x]

不对。这题搞得我现在有点懵，这会正好感冒昏昏沉沉的😵‍💫等我二编…

完整代码

53.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解题思路

经典解法：Kadane算法。核心思路是动态规划，通过遍历数组维护当前最大子数组和。整体思路如下：
1️⃣维护两个变量：

  • sum当前最大子数组和
  • maxsum全局最大子数组和
    2️⃣遍历数组，每次决定是否扩展当前子数组
  • 如果sum+nums[i] < nums[i] 从nums[i]重新开始（之前的子数组必定与最大和无关
  • 否则继续累加nums[i]
    3️⃣每次更新maxsum

完整代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=nums[0];
        int maxsum=nums[0];
        for(int i=1;i<nums.size();i++){
            sum=max(nums[i],sum+nums[i]);
            maxsum=max(sum,maxsum);
        }
        return maxsum;
    }
};