力扣刷题动态规划篇章

2770. 达到末尾下标所需的最大跳跃次数

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

  • 0 <= i < j < n
  • -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(n, -1);
        f[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] != -1 && abs(nums[i] - nums[j]) <= target) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return f[n - 1];
    }
};

2915. 和为目标值的最长子序列的长度

给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。

返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

示例 1：

1
2
3
输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。

示例 2：

1
2
3
输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。

示例 3：

1
2
3
输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：无法得到和为 3 的子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) 
    {
        int n = nums.size();
        const int INF = 1e9;
        int f[target + 1];
        for (int i = 0; i <= target; i++) f[i] = -INF;
        f[0] = 0;
        for (int i = 0; i < n; i++) 
            for (int j = target; j >= nums[i]; j--) 
                f[j] = max(f[j], f[j - nums[i]] + 1);
        return max(-1, f[target]);
    }
};

2826. 将三个组排序

给你一个整数数组 nums 。nums 的每个元素是 1，2 或 3。在每次操作中，你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。

示例 1：

1
2
3
4
输入：nums = [2,1,3,2,1]
输出：3
解释：
其中一个最优方案是删除 nums[0]，nums[2] 和 nums[3]。

示例 2：

1
2
3
4
输入：nums = [1,3,2,1,3,3]
输出：2
解释：
其中一个最优方案是删除 nums[1] 和 nums[2]。

示例 3：

1
2
3
4
输入：nums = [2,2,2,2,3,3]
输出：0
解释：
nums 已是非递减顺序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<int> dp(3,0);
        for(int i=0;i<nums.size();i++)
        {
            int cur=nums[i]-1;
            for(int j=cur;j>=0;j--) dp[cur]=max(dp[cur],dp[j]+1);
        }
        int Maxn=0;
        for(int i=0;i<3;i++) Maxn=max(dp[i],Maxn);
        return nums.size()-Maxn;
    }
};
//f(n)=max(f(1),f(2),f(n))......若n为2

2786. 访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

  • 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
  • 对于你访问的位置 i ，你可以获得分数 nums[i] 。
  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

示例 1：

1
2
3
4
5
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

1
2
3
4
输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();
        const long long INF = 1e18;
        long long f[2];
        f[0] = f[1] = -INF;
        f[nums[0] % 2] = nums[0];
        // 从左到右枚举访问的终点
        long long ans = nums[0];
        for (int i = 1; i < n; i++) 
        {
            // 套用 dp 方程
            int p = nums[i] % 2;
            long long t = max(f[p] + nums[i], f[p ^ 1] + nums[i] - x);
            f[p] = max(f[p], t);
            ans = max(ans, t);
        }
        return ans;
    }
};

2944. 购买水果需要的最少金币数

你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。

给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

  • 如果你花费 price[i] 购买了水果 i ，那么后面的 i 个水果你可以免费获得。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

1
2
3
4
5
6
7
8
输入：prices = [3,1,2]
输出：4
解释：你可以按如下方法获得所有水果：
- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。
- 免费获得水果 3 。
注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。
购买所有水果需要最少花费 4 个金币。

示例 2：

1
2
3
4
5
6
7
8
输入：prices = [1,10,1,1]
输出：2
解释：你可以按如下方法获得所有水果：
- 花 1 个金币购买水果 1 ，然后免费获得水果 2 。
- 免费获得水果 2 。
- 花 1 个金币购买水果 3 ，然后免费获得水果 4 。
- 免费获得水果 4 。
购买所有水果需要最少花费 2 个金币。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            /* 选择买当前水果的花费 */
            int buy = f[i - 1] + prices[i - 1];
            f[i] = min(f[i], buy);

            /* 如果买了当前水果, 后面i个水果可以免费获得, 更新后面的最小值 */
            for (int j = 1; j <= i && i + j <= n; j++) {
                f[i + j] = min(f[i + j], buy);
            }
        }
        return f[n];
    }
};