~~区间DP为什么不用记忆化搜索的写法呢~~
我总觉得这样写会漏情况或多情况，用记忆华搜索的写法更容易debug
by AsunderSquall @ 2020-10-17 08:57:03
@[我知道了王子](/user/70132) ~~我是为了复习区间 dp 才用区间 dp 做的这题啊~~
我漏了哪些情况或者多了哪些情况啊 qwq
by 一只书虫仔 @ 2020-10-17 08:59:23
@[一只书虫仔](/user/114914) 感觉写反了？相等不加1吧（错了轻喷）
by zhanghzqwq @ 2020-10-17 09:07:38
@[zhanghanzhang](/user/219668) 改过来都输出 $n$
by 一只书虫仔 @ 2020-10-17 09:08:39
@[一只书虫仔](/user/114914) 诶？我也是输出n啊
by zhanghzqwq @ 2020-10-17 09:11:24
递推公式真的对吗（感觉好像有问题）
为什么$s_i=s_k$则可以以$dp(i,k)+dp(k+1,j)+1$的代价更新？
感觉比较$s_i$和$s_k$没什么意义啊
by jerrywcy @ 2020-10-17 09:11:27
@[一只书虫仔](/user/114914) 相等不加1，且状态转移的`j`改为`j-1`
by shenmadongdong @ 2020-10-17 09:12:46
@[jerrywcy](/user/21878) 相同代表可以删除啊
如果不对的话我再想想
by 一只书虫仔 @ 2020-10-17 09:12:57
我错了
但我感觉应该是两个改过来
by jerrywcy @ 2020-10-17 09:13:37
@[shenmadongdong](/user/71491) 感谢，但是只对了前 4 个，WA 了
```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int main () {
int n;
char s[505];
scanf("%d", &n);
scanf("%s", s);
for (int len = 0; len < n; len++)
for (int i = 0; i < n - len + 1; i++) {
int j = i + len;
int Min = 0x3f3f3f3f;
if (i == j) {
dp[i][j] = 1;
continue;
}
for (int k = i; k < j; k++) {
if (s[i] == s[k]) Min = min(Min, dp[i][k] + dp[k + 1][j - 1]);
else Min = min(Min, dp[i][k] + dp[k + 1][j - 1] + 1);
}
dp[i][j] = Min;
}
printf("%d", dp[0][n - 1]);
return 0;
}
```
by 一只书虫仔 @ 2020-10-17 09:14:15