public class Solution
{
public int MinCut(string s)
{
if (s.Length == 0)
return 0;
var part = new bool[s.Length, s.Length];
part[0, 0] = true;
for (var i = 1; i < s.Length; i++)
part[i, i] = part[i, i - 1] = true;
for (var i = 1; i < s.Length; i++)
for (var j = 0; j < s.Length - i; j++)
part[j, i + j] = part[j + 1, i + j - 1] && s[j] == s[i + j];
// 这一段原本我是用131的的Foo()改的,结果超时了。按官方的解法写了如下代码
var f = new int[s.Length];
Array.Fill(f, s.Length);
for (var i = 0; i < s.Length; i++)
if (part[0, i])
f[i] = 0;
else
for (var j = 0; j < i; j++)
if (part[j + 1, i])
f[i] = Math.Min(f[i], f[j] + 1);
return f[^1];
}
}