1 题目---------------------------------------------------------------------
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
例子：
输入：n = 2, rollMax = [1,1,2,2,2,3] 输出：34 解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
输入：n = 2, rollMax = [1,1,1,1,1,1] 输出：30
输入：n = 3, rollMax = [1,1,1,2,2,3] 输出：181
// 解题思路---------------------------------------------------------------------
/*
dp[i][j]的值代表第i个骰子，结尾的数字是j的次数 那么我们的结果就是dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4]+dp[n][5]+dp[n][6]
动态转移方程就是 dp[i][j]=∑dp[i-L][k！=j] 其中 1<=L<=rollMax[j-1] 1<=k<=6 连续 掷出数字 j 的次数不能超过 rollMax[j]
_ _ _ _ 2 假如rollMax[j-1]=1 那么倒数第二个位置就不能为2 dp[i][j]+=dp[i-1][k！=j]
如果rollMax[j-1]=2 倒数第二个位置和倒数第三个位置不能为2 dp[i][j]+=dp[i-1][k！=j]+dp[i-2][k！=j]
如果rollMax[j-1]大于等于骰子数i 显然不可能扔出这种情况，那么dp[i][j]=∑dp[i-1][k]
*/
//结果可能非常大，设置取mod常数
const int P = 1e9 + 7;
int dieSimulator(int n, vector<int>& rollMax) {
//初始化数组(n不是常量，所以这里不够严谨）
int dp[n + 1][7];
memset(dp, 0, sizeof(dp));
dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = dp[1][6] = 1;
//开始循环
for (int i = 1;i <= n;++i) //第一重 代表骰子数
{
for (int j = 1;j <= 6;++j) //第二重 代表以j为结尾
{
for (int k = 1;k <= 6;++k) //第三重和第四重 用来求和
{
for (int l = 1;l <= rollMax[j - 1];++l)
{
if (rollMax[j - 1] >= i)
{
//如果不超过的次数大于骰子数，那么dp[i][j]+=dp[i-1][k]
dp[i][j] = (dp[i][j] % P + dp[i - 1][k] % P) % P;
break;
}
else
{
//dp[i][j]+=dp[i-1][k] 其中k不等于j
if (i - l > 0 && k != j)
{
dp[i][j] = (dp[i][j] % P + dp[i - l][k] % P) % P;
}
}
}
}
}
}
return ((((((dp[n][1] % P + dp[n][2] % P) % P + dp[n][3] % P) % P + dp[n][4] % P) % P + dp[n][5] % P) % P + dp[n][6] % P) % P) % P;
}
2 题目---------------------------------------------------------------------
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
例子：
输入：arr = [1,2,3,4], difference = 1 输出：4 解释：最长的等差子序列是 [1,2,3,4]。
输入：arr = [1,3,5,7], difference = 1 输出：1 解释：最长的等差子序列是任意单个元素。
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2 输出：4 解释：最长的等差子序列是 [7,5,3,1]。
1 <= arr.length <= 10^5-10^4 <= arr[i], difference <= 10^4
// 解题思路---------------------------------------------------------------------
int longestSubsequence(vector<int>& arr, int difference) {
int len = arr.size();
if (len == 0)
return 0;
if (len == 1)
return 1;
//动态规划初始化
int dp[20010] = { 0 };
dp[0] = 0;
//保存最大长度
int temp = -1;
//先把元素值变为正数
for (int i = len - 1;i >= 0;--i)
{
arr[i] += 10000;
}
//状态转移方程 从后往前，dp[arr[i]]=dp[arr[i] + difference]+1
for (int i = len - 1;i >= 0;--i)
{
//如果数组越界直接置为1 因为该值只能是等差数列边界值
if (arr[i] + difference < 0 || arr[i] + difference>20000)
{
dp[arr[i]] = 1;
continue;
}
dp[arr[i]] = dp[arr[i] + difference] + 1;
//取最大长度
temp = max(temp, dp[arr[i]]);
}
return temp;
}
3 题目---------------------------------------------------------------------
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
例子：
输入：s = "abcd", t = "bcdf", cost = 3 输出：3 解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
输入：s = "abcd", t = "acde", cost = 0 输出：1 解释：你无法作出任何改动，所以最大长度为 1。
1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6s和t都只含小写英文字母。
// 解题思路---------------------------------------------------------------------
int equalSubstring(string s, string t, int maxCost) {
int lens = s.size();
if (lens == 0)
return 0;
//保存每个位置的cost 题目转变成就最长子数组（不需要连续）的和不大于cost
vector<int>res;
for (int i = 0;i < lens;++i)
{
res.push_back(abs(s[i] - t[i]));
}
//前缀和数组
int dp[lens + 1]; //这里可以使用vector
dp[0] = 0;
int ans = 0;
//求以第i个字符为结尾的cost 因为元素都非负数，其实就是前缀和
for (int i = 1;i <= lens;++i)
{
dp[i] = dp[i - 1] + res[i - 1];
}
//遍历区间（j，i)的总cost不大于maxCost的情况中的最大距离。
for (int i = 1, j = 0;i <= lens;++i)
{
//当遍历到第一个dp[i]-dp[0]>maxCost时，j指针从0向前移动，直到dp[i] - dp[j]<= maxCost
for (;dp[i] - dp[j] > maxCost;++j);
ans = max(ans, i - j);
}
return ans;
}
4 题目---------------------------------------------------------------------
/*
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
请看示例：
示例 1：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：
输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。
示例 3：
输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
*/
// 解题思路---------------------------------------------------------------------
int maximumSum(vector<int>& arr) {
int len = arr.size();
int _max = -100001;
int _min = 100001;
int sum = 0;
//处理特殊情况
for (int i = 0;i < len;++i)
{
if (arr[i] > _max)
_max = arr[i];
if (arr[i] < _min)
_min = arr[i];
sum += arr[i];
}
//如果全是负数返回最大值
if (_max <= 0)
return _max;
//如果全是正数返回总和
if (_min >= 0)
return sum;
sum = 0;
//动态规划数组 第一维表示前i位置最大和，第二维是0的时候表示未删除元素，是1的时候代表已经删除了元素
int dp[len + 1][2];
memset(dp, 0, sizeof(dp));
for (int i = 1;i <= len;++i)
{
//arr[i - 1]代表第i个元素的值
//没删除元素 类似求最大子数组
dp[i][0] = max(arr[i - 1], arr[i - 1] + dp[i - 1][0]);
//有删除元素，那么删除i就是dp[i][1]=dp[i-1][0] 不删除i那么就是dp[i][1]=dp[i - 1][1] + arr[i - 1]
dp[i][1] = max(dp[i - 1][1] + arr[i - 1], dp[i - 1][0]);
//不断求最大值
sum = max(sum, max(dp[i][0], dp[i][1]));
}
return sum;
}