力扣 (区间 dp 专题1)
1312让字符串成为回文串的最小插入次数
链接:*********************************************************************
定义 区间 dp[left][right],首先我们要明确最终要求的是 dp[0][n - 1]。 很容易想到动态规划,但从递归入手为优解。 首先要知道递归出口,也就是基础情况:只剩一个字符,必为回文,不动;剩两个字符,相同字符则回文,不动,不同只需操作一次即可;
- if(left == right) return 0;
- if(left + 1 == right) return s[left] == s[right] ? 0 : 1;
一般情况的讨论其实也简单,就不赘述了,直接上代码 递归 + 记忆化搜索
:
Code
int f1(char* s, int** dp, int left, int right) {
if(dp[left][right] != -1) return dp[left][right];
if(left == right) return 0;
if(left + 1 == right) return s[left] == s[right] ? 0 : 1;
if(s[left] == s[right]) {
dp[left][right] = f1(s, dp, left + 1, right - 1);
} else {
int p1 = f1(s, dp, left, right - 1) + 1;
int p2 = f1(s, dp, left + 1, right) + 1;
dp[left][right] = p1 < p2 ? p1 : p2;
}
return dp[left][right];
}
int minInsertions(char* s) {
int n = strlen(s);
int** dp = malloc(sizeof(int*) * n);
for(int i = 0; i < n; i++) {
dp[i] = malloc(sizeof(int) * n);
memset(dp[i], -1, sizeof(int) * n);
}
int ans = f1(s, dp, 0, n - 1);
for(int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return ans;
}
从递归写起,改成动态规划就很简单了,直接贴代码:
Code
int minInsertions(char* s) {
int n = strlen(s);
int** dp = malloc(sizeof(int*) * n);
for(int i = 0; i < n; i++) {
dp[i] = calloc(n, sizeof(int));
}
// 初始化
for(int i = 0; i < n - 1; i++) {
dp[i][i + 1] = s[i] == s[i + 1] ? 0 : 1;
}
for(int i = n - 3; i >= 0; i--) {
for(int j = i + 2; j < n; j++) {
if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
else {
int p1 = dp[i + 1][j] + 1;
int p2 = dp[i][j - 1] + 1;
dp[i][j] = p1 < p2 ? p1 : p2;
}
}
}
int ans = dp[0][n - 1];
for(int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return ans;
}
当然可以进行空间优化,一维数组滚动,很机械化,写了很多遍了,这里就不写了。 , 第一题还是写一下吧
Code
// 空间压缩
int minInsertions(char* s) {
int n = strlen(s);
int* dp = calloc(n, sizeof(int) * n);
for(int i = n - 2; i >= 0; i--) {
int prev = 0;
dp[i + 1] = s[i] == s[i + 1] ? 0 : 1;
for(int j = i + 2; j < n; j++) {
int temp = dp[j];
if(s[i] == s[j]) dp[j] = prev;
else {
int p1 = dp[j - 1] + 1;
int p2 = dp[j] + 1;
dp[j] = p1 < p2 ? p1 : p2;
}
prev = temp;
}
}
int ans = dp[n - 1];
free(dp);
return ans;
}
486预测赢家
链接:bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
博奕类问题,每个人都会利益最大化(并不是简单的贪心)。直接上代码解释。个人认为还是挺难想的,哈哈~~~~
Code
// 递归 + 记忆化搜索
// 这个函数返回值是玩家1所能得到的最大分数
int f1(int* nums, int** dp, int left, int right) {
if(dp[left][right] != -1) return dp[left][right];
if(left == right) return nums[left];
if(left + 1 == right) return nums[left] < nums[right] ? nums[right] : nums[left];
// p1 p2 为玩家1在不同选择下玩家2使出的对自己最优策略,导致玩家1在玩家2选择后有一个对自己(玩家1)劣势局面
int p1 = nums[left] + fmin(f1(nums, dp, left + 2, right), f1(nums, dp, left + 1, right - 1));
int p2 = nums[right] + fmin(f1(nums, dp, left, right - 2), f1(nums, dp, left + 1, right - 1));
dp[left][right] = fmax(p1, p2); // 玩家1优解策略
return dp[left][right];
}
bool predictTheWinner(int* nums, int numsSize) {
int sum = 0;
for(int i = 0; i < numsSize; i++) {
sum += nums[i];
}
int** dp = malloc(sizeof(int*) * numsSize);
for(int i = 0; i < numsSize; i++) {
dp[i] = malloc(sizeof(int) * numsSize);
memset(dp[i], -1, sizeof(int) * numsSize);
}
int a1 = f1(nums, dp, 0, numsSize - 1); // a1 是玩家1得到的分数
int a2 = sum - a1; // a2 是玩家2得到的分数
return a1 >= a2;
}
有了递归,改成动态规划就不难了,直接上代码:
Code
bool predictTheWinner(int* nums, int numsSize) {
int sum = 0;
for(int i = 0; i < numsSize; i++) {
sum += nums[i];
}
int** dp = malloc(sizeof(int*) * numsSize);
for(int i = 0; i < numsSize; i++) {
dp[i] = calloc(numsSize, sizeof(int));
}
// 初始化
for(int i = 0; i < numsSize; i++) {
dp[i][i] = nums[i];
if(i + 1 < numsSize) {
dp[i][i + 1] = nums[i] < nums[i + 1] ? nums[i + 1] : nums[i];
}
}
for(int i = numsSize - 3; i >= 0; i--) {
for(int j = i + 2; j < numsSize; j++) {
int p1 = nums[i] + (dp[i + 2][j] < dp[i + 1][j - 1] ? dp[i + 2][j] : dp[i + 1][j - 1]);
int p2 = nums[j] + (dp[i][j - 2] < dp[i + 1][j - 1] ? dp[i][j - 2] : dp[i + 1][j - 1]);
dp[i][j] = p1 < p2 ? p2 : p1;
}
}
int ans = dp[0][numsSize - 1];
for(int i = 0; i < numsSize; i++) {
free(dp[i]);
}
free(dp);
int a1 = ans; // a1 是玩家1得到的分数
int a2 = sum - a1; // a2 是玩家2得到的分数
return a1 >= a2;
}
1039多边三角形剖分的最低得分
链接:ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
说实话确实不是很好想,第一次做此类题的话确实难,但做过一次后应当有所长进,熟能生巧。区间 dp[left][right]: 左右顶点作为区间的左右边界,通过枚举第三个顶点,选取最优解。
Code
// 递归 + 记忆化搜索
int f1(int* values, int** dp, int left, int right) {
// 递归出口(边界情况)
if(dp[left][right] != -1) return dp[left][right];
if(left == right || left + 1 == right) return 0; // 不存在一个或两个顶点的情况。
int ans = INT_MAX;
// 枚举行为:枚举第三个顶点,接着再调用递归(大问题化小问题)
// 注意第三个顶点只能在左右边界两个顶点之间枚举!ans 为每次枚举后比较下来的最优解。
for(int mid = left + 1; mid < right; mid++) {
ans = fmin(ans, f1(values, dp, left, mid) + f1(values, dp, mid, right) + values[mid] * values[left] * values[right]);
}
dp[left][right] = ans;
return dp[left][right];
}
int minScoreTriangulation(int* values, int valuesSize) {
int** dp = malloc(sizeof(int*) * valuesSize);
for(int i = 0; i < valuesSize; i++) {
dp[i] = malloc(sizeof(int) * valuesSize);
memset(dp[i], -1, sizeof(int) * valuesSize);
}
int ans = f1(values, dp, 0, valuesSize - 1);
for(int i = 0; i < valuesSize; i++) {
free(dp[i]);
}
free(dp);
return ans;
}
动态规划版本:
Code
int minScoreTriangulation(int* values, int valuesSize) {
int** dp = malloc(sizeof(int*) * valuesSize);
for(int i = 0; i < valuesSize; i++) {
dp[i] = calloc(valuesSize, sizeof(int));
}
// 其实就是由递归演变而来。
for(int i = valuesSize - 3; i >= 0; i--) {
for(int j = i + 2; j < valuesSize; j++) {
int min_val = INT_MAX;
for(int k = i + 1; k < j; k++) {
int temp = dp[i][k] + dp[k][j] + values[i] * values[j] * values[k];
min_val = min_val < temp ? min_val : temp;
}
dp[i][j] = min_val;
}
}
int ans = dp[0][valuesSize - 1];
for(int i = 0; i < valuesSize; i++) {
free(dp[i]);
}
free(dp);
return ans;
}