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