【动态规划】区间DP

基本思路

将大范围的问题拆分为若干小范围来求解

可能展开的常见方式如下：

• 基于两侧端点讨论的可能性展开
• 基于范围上划分点的可能性展开

例题

字符串成为回文串的最小操作次数

https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome

• 最小的区间，相邻字符串相等时，一定是回文串
• 往大了看，对于区间\([l,r]\)，若l与r相等，则可以直接对上，此时只需要转移到区间\([l+1,r-1]\)继续考虑即可
• 若不相等，有两种情况
  • 第一个是保持左区间不变，在右区间后花费一点代价置入一个与l处相同的字符，并转移到区间\([l+1,r]\)继续考虑
  • 第二个是保持右区间不变，在左区间前花费一点代价置入一个与r处相同的字符，并转移到区间\([l,r-1]\)继续考虑

​ 两个情况求最小

令dp[l][r]是区间l与r之间形成回文串所需要的代价

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int minInsertions(string s) {
   int n = s.size();
   s = ' '+s;
   vector<vector<int>> dp(n+1, vector<int>(n+1,0));
   for (int i = 1; i<n; i++)
   {
    if(s[i]==s[i+1])
    {
        dp[i][i+1] = 0;
    }
    else
    {
        dp[i][i+1] = 1;
    }
   }
   for (int l = n-2; l>=1; l--)
   {
        for (int r = l+2; r<=n; r++)
        {
            if (s[l]==s[r])
            {
                dp[l][r] = dp[l+1][r-1];
            }
            else
            {
                dp[l][r] = min(dp[l+1][r], dp[l][r-1])+1;
            }
        }
   }
   return dp[1][n]; 
}

预测赢家

https://leetcode.cn/problems/predict-the-winner/

假设每个玩家以最优策略进行游戏，我们可以看作零和博弈

• 剩一个数，玩家1先拿
• 剩两个数，玩家1拿大的
• 剩多个数， 假设数组为nums
  • 若玩家一从左边拿，即拿nums[l]，则玩家2可以拿nums[l+1]或nums[r]，且玩家2一定会选择留给玩家1剩余数更少的那种情况
  • 若玩家一从右边拿，即拿nums[r]，则玩家2可以拿nums[l]或nums[r-1]，且玩家2一定会选择留给玩家1剩余数更少的那种情况
  • 玩家一会在上面两种情况中选择对自己更好的选择，即选max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool predictTheWinner(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n,0));
    int sum = accumulate(nums.begin(), nums.end(), 0);
    for (int i = 0; i<n-1; i++)    
    {
        dp[i][i] = nums[i];
        dp[i][i+1] = max(nums[i], nums[i+1]);
    }
    dp[n-1][n-1] = nums[n-1];
    for (int l = n-3; l>=0; l--)
    {
        for (int r = l+2; r<n; r++)
        {
            dp[l][r] = max(
                nums[l] + min(dp[l+1][r-1], dp[l+2][r]),
                nums[r] + min(dp[l][r-2], dp[l+1][r-1])
            );
        }
    }
    int a = dp[0][n-1];
    int b = sum-a;
    return a>=b;
}

多边形三角剖分的最低得分

https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/

我们发现，n顶点的多边形能划分出n-2个三角形

因此我们可以枚举划分点，选第0与n-1个顶点作为底，这俩一定会组成一个三角形：

• 划分点为1，计算得分为0,1,n-1构成三角形得分+1到5范围上拆分出的三角形得分
• 划分点为2，计算得分为0,2,n-1构成三角形得分+0到2范围上拆分出的三角形得分+2到5范围上拆分出的三角形得分
• 以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int minScoreTriangulation(vector<int>& values) {
    int n = values.size();
    vector<vector<int>> dp(n, vector<int>(n));
    for (int l = n-3; l>=0; l--)
    {
        for(int r = l+2; r<n; r++)
        {
            dp[l][r] = INT_MAX;
            for(int m = l+1; m<r; m++)
            {
                dp[l][r] = min(dp[l][r], dp[l][m]+dp[m][r]+values[l]*values[m]*values[r]);
            }
        }
    }
    return dp[0][n-1];
}

切棍子的最小成本

要决定一个顺序，使得切棍子代价最小

由于可以重排，我们可以直接从小到大排序，然后将棍子头尾加进来

则在l与r间的某个位置m切割，获得的代价即为l-1到r+1间的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int minCost(int n, vector<int>& cuts) {
    int m = cuts.size();
    sort(cuts.begin(), cuts.end());
    vector<int> interv;
    interv.push_back(0);
    for(auto it:cuts)
    {
        interv.push_back(it);
    }
    interv.push_back(n);
    vector<vector<int>> dp(m+2, vector<int>(m+2));
    for (int i = 1; i<=m; i++)
    {
        dp[i][i] = interv[i+1]-interv[i-1];
    }
    for (int l = m-1; l>=1; l--)
    {
        for (int r = l+1; r<=m; r++)
        {
            dp[l][r] = INT_MAX;
            for(int k = l; k<=r; k++)
            {
                dp[l][r] = min(dp[l][r], dp[l][k-1]+dp[k+1][r]+interv[r+1]-interv[l-1]);
            }
        }
    }
    return dp[1][m];

}