解析思路
leetcode 中等难度,题目描述点击这里。
经过分割回文数后,本题应该就比较简单了。
题目要求返回最少的分割次数,通常这类最优问题都可以用 dp 来解决。注意这里无法使用上题的 dfs 暴力穷举所有结果后找到最优,会超时(因为字符长度最大为 2000,上题为 16)。
如果要用 dp 那么就需要构建 dp 表达式:
定义 minC[k]表示从 0 到 k 的最小分割次数,递推关系如下:
- minC[k] = 0 ,k==0 || dp[0][k],当 k=0 或者 0-k 是一个回文串
- minC[k] = min(min[r-1]+1).其他情况需要在 0 到 k 之间找到一个 r 使 r 到 k 为一个回文数,那么分割次数就是 minC[r-1]+1(0 到 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 30 31 32 33 34 35 36 37 38 39
| public class Q132 {
public int minCut(String s) { boolean[][] dp = new boolean[s.length()][s.length()]; for (int j = 0; j < dp.length; j++) { for (int i = 0; i <= j; i++) { if (i == j) { dp[i][j] = true; } else { boolean b = s.charAt(i) == s.charAt(j); if (i + 1 == j) { dp[i][j] = b; } else { dp[i][j] = dp[i + 1][j - 1] && b; } } } } int[] minArr = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int temp = i; for (int l = 0; l <= i; l++) { if (dp[l][i]) { temp = Math.min(temp, l == 0 ? 0 : minArr[l - 1] + 1); } } minArr[i] = temp; } return minArr[s.length() - 1]; }
public static void main(String[] args) { System.out.println(new Q132().minCut("aab")); } }
|
如果本篇文章对您有帮助欢迎打赏哦!
关注公众号(烦嚣的人)