力扣 (区间 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;
}


全部评论

相关推荐

06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务