基本思路
将大范围的问题拆分为若干小范围来求解
可能展开的常见方式如下：
- 基于两侧端点讨论的可能性展开
- 基于范围上划分点的可能性展开
例题
字符串成为回文串的最小操作次数
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome
- 最小的区间，相邻字符串相等时，一定是回文串
- 往大了看，对于区间，若l与r相等，则可以直接对上，此时只需要转移到区间继续考虑即可
- 若不相等，有两种情况
- 第一个是保持左区间不变，在右区间后花费一点代价置入一个与l处相同的字符，并转移到区间继续考虑
- 第二个是保持右区间不变，在左区间前花费一点代价置入一个与r处相同的字符，并转移到区间继续考虑
两个情况求最小
令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];
}
|
