力扣10.19

3192. 使二进制数组全部等于 1 的最少操作次数 II

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。

数据范围

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 1

分析

考虑10110这个元素，要使下标为[2:]的元素均为1，必须得先把[3:]的元素变为0，因此考虑从尾向头遍历，若当前位置为1且不是首部，则反转它和后面的，若当前位置为0，也进行翻转

代码

class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size();int res = 0;for(int i = n - 1; i >= 0; i -- ) {int j = i;while(j >= 0) {if(nums[j] == nums[i]) j -- ;else break;}i = j + 1;if(nums[i] == 1 && i != 0) res ++ ;else if(nums[i] == 0) res ++ ;  }return res;}
};

---

741. 摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

• 0 表示这个格子是空的，所以你可以穿过它。

• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。

• -1 表示这个格子里有荆棘，挡着你的路。
  请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

• 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；

• 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；

• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；

• 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

数据范围

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• grid[i][j] 为 -1、0 或 1
• grid[0][0] != -1
• grid[n - 1][n - 1] != -1

分析

从$(0,0)$出发到$(n-1,n-1)$再返回$(0,0)$，可以相当于从两个机器人同时从(0,0)出发到达$(n-1,n-1)$，观察一下数据范围，只有50，因此可以直接将两个机器人的状态作为dp,令$dp[x1][y1][x2][y2]$表示机器人1和2分别位于$(x1,y1),(x2,y2)$时收集的樱桃总和，使用记忆化搜索的方式会更加简单

• $dfs(x1,y1,x2,y2)=max(dfs(x1,y1-1,x2,y2-1),dfs(x1,y1-1,x2-1,y2),dfs(x1-1,y1,x2-1,y2),dfs(x1-1,y1,x2,y2-1)+c$，c为这次当前位置两个机器人收获的樱桃

代码

class Solution {
public:const static int N = 55;int dp[N][N][N][N];int dx[2] = {0, 1};int dy[2] = {1, 0};int n, m;int dfs(int x1, int y1, int x2, int y2, vector<vector<int>>& grid) {if(x1 == n - 1 && y1 == m - 1 && x2 == n - 1 && y2 == m - 1) return grid[x1][y1];if(x1 < 0 || x2 < 0 || x1 >= n || x2 >= n || y1 < 0 || y2 < 0 || y1 >= m || y2 >= m) return -0x3f3f3f3f;if(grid[x1][y1] == -1 || grid[x2][y2] == -1) return -0x3f3f3f3f;int& t = dp[x1][y1][x2][y2];if(t != -1) return t;t = 0;int c;if(x1 == x2 && y1 == y2) c = grid[x1][y1];else c = grid[x1][y1] + grid[x2][y2];int tmpt = -0x3f3f3f3f;for(int i = 0; i < 2; i ++ ) {for(int j = 0; j < 2; j ++ ) {tmpt = max(tmpt, dfs(x1 + dx[i], y1 + dy[i], x2 + dx[j], y2 + dy[j], grid));}}t = tmpt + c;return t;}int cherryPickup(vector<vector<int>>& grid) {n = grid.size();m = grid[0].size();memset(dp, -1, sizeof(dp));int res = dfs(0, 0, 0, 0, grid);if(res < 0) return 0;return res;}
};

---

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

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

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

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

数据范围

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 1 <= target <= 1000

分析

01背包，将每个数的价值看作是1，背包容量为target，令dp[i][j]为前i个数容量正好为j是的长度，这道题和普通01背包不同就在于需要正好是j，因此需要将其他的不合法状态设置为一个极小值，其他就按照正常01背包套路来写，然后可以利用轮动数组优化一下

代码

class Solution {
public:const static int N = 1005;int dp[N];int lengthOfLongestSubsequence(vector<int>& nums, int target) {int n = nums.size();memset(dp, -0x3f, sizeof(dp));dp[0] = 0;for(int i = 0; i < n; i ++ ) {for(int j = target; j >= nums[i]; j -- ) {dp[j] = max(dp[j], dp[j - nums[i]] + 1);}}return dp[target] < 0 ? -1 : dp[target];}
};

---

2787. 将一个数字表示成幂的和的方案数

给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3，一个表示 n 的方法是 n = 23 + 33 + 53 。

数据范围

• 1 <= n <= 300
• 1 <= x <= 5

分析

令dp[i][j]为前i个数的x次方里，满足总和为j的方案数，由于n最大为300，因此快速幂处理i的x次方时可以将超过300的部分返回301，接下来是状态转移

• $dp[i][j]+=dp[i-1][j]+dp[i-1][j-qpow(i,x)]$
  同样这题可以通过滚动数组进行优化

代码

typedef long long LL;
class Solution {
public:const static int N = 305, mod = 1e9 + 7;int dp[N];LL qpow(LL a, LL n) {LL res = 1;while(n) {if(res > 300 || a  > 300) return 301;if(n & 1) res = res * a;a = a * a;n >>= 1;}return res;}int numberOfWays(int n, int x) {dp[0] = 1;for(int i = 1; i <= n; i ++ ) {for(int j = n; j >= qpow(i, x); j -- ) {dp[j] += dp[j - qpow(i,x)];dp[j] %= mod;}}return dp[n];}
};

---

3180. 执行操作可获得的最大总奖励 I

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即x = x + rewardValues[i]），并 标记 下标 i。
  以整数形式返回执行最优操作能够获得的 最大 总奖励。

数据范围

• 1 <= rewardValues.length <= 2000
• 1 <= rewardValues[i] <= 2000

分析

• 首先，若先选最大的数，那就选不了小的数，因此贪心的思路肯定是从小往大选，先排序

• 考虑最大的值会不会选，假如不选，则将选的最大值替换为全局最大值一定会更优，因此最大值一定被选，假设最大值为k，则前$n-1$个物品就构成了01背包问题。

• 接下来考虑背包容量，体积和价值分别是什么，首先，要想装下最后一个数k，因此前面的价值之和不能超过$k-1$，因此背包容量为$k-1$，体积和价值都为数的大小

• 接下来考虑状态定义，令dp[i][j]为前i个数，总体积不超过j时价值的最大值

• 然后是状态转移，对前n-1个数进行01背包，但这里需要注意，原始的01背包是$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)$，即分为选或不选两种情况，若选则从上一个状态j-w转移过来，但这题有限制，$dp[i-1][j-w]$的价值不一定比w小，因此状态转移暂定如下

  • $dp[i][j]=max(dp[i-1][j],dp[i-1][c]+w)$

• 接下来考虑$c$的取值，首先，本体价值和体积相同，因此对于状态$dp[i][w]$，其价值v必然不会大于$w$，考虑到这一点，上一个状态$j-w$的价值也不会大于$j-w$，因此对$j-w$进行讨论

  • 若$j-w>=w$，此时$c$取$w-1$，因为最大不能取j-w
  • 若$j-w<w$，此时$c$取$j-w$

• 最终答案为$dp[n-1][k-1]+k$
  同样这题可以用滚动数组进行优化
  下面的代码1为没有空间优化的代码，代码2进行轮动数组优化

代码1

class Solution {
public:const static int N = 2005;int dp[N][N];int maxTotalReward(vector<int>& rewardValues) {int n = rewardValues.size();sort(rewardValues.begin(), rewardValues.end());int t = rewardValues.back();for(int i = 0; i < n - 1; i ++ ) {for(int j = 0; j < t; j ++ ) {dp[i + 1][j] = dp[i][j];if(j >= rewardValues[i]) {int c;if(j - rewardValues[i] >= rewardValues[i]) c = rewardValues[i] - 1;else c = j - rewardValues[i];dp[i + 1][j] = max(dp[i][j], dp[i][c] + rewardValues[i]);}}}return dp[n - 1][t - 1] + t;}
};

代码2

class Solution {
public:const static int N = 2005;int dp[N];int maxTotalReward(vector<int>& rewardValues) {int n = rewardValues.size();sort(rewardValues.begin(), rewardValues.end());int t = rewardValues.back();for(int i = 0; i < n - 1; i ++ ) {for(int j = t - 1; j >= rewardValues[i]; j -- ) {int c;if(j - rewardValues[i] >= rewardValues[i]) c = rewardValues[i] - 1;else c = j - rewardValues[i];dp[j] = max(dp[j], dp[c] + rewardValues[i]);}}return dp[t - 1] + t;}
};