LeetCode: Palindrome Partitioning II

dfs large没过，看了网上的dp

 1 class Solution {
 2 public:
 3     int minCut(string s) {
 4         int n = s.size();
 5         vector<int> C(n+1);
 6         vector<vector<bool> > P(n, vector<bool>(n));
 7         for (int i = 0; i < n; ++i) P[i][i] = true;
 8         for (int i = 0; i <= n; ++i) {
 9             C[i] = n - i;
10         }
11         for (int i = n-1; i >= 0; --i) {
12             for (int j = i; j < n; ++j) {
13                 if (s[i] == s[j] && (j-i < 2 || P[i+1][j-1])) {
14                     P[i][j] = true;
15                     C[i] = min(C[i], 1+C[j+1]);
16                 }
17             }
18         }
19         return C[0]-1;
20     }
21 };

 1 public class Solution {
 2     public int MinCut(string s) {
 3         int n = s.Length;
 4         int[] C = new int[n+1];
 5         bool[,] P = new bool[n, n];
 6         for (int i = 0; i < n; i++) P[i, i] = true;
 7         for (int i = 0; i <= n; i++) C[i] = n - i;
 8         for (int i = n-1; i >= 0; i--) {
 9             for (int j = i; j < n; j++) {
10                 if (s[i] == s[j] && (j-i < 2 || P[i+1, j-1])) {
11                     P[i, j] = true;
12                     C[i] = Math.Min(C[i], 1 + C[j+1]);
13                 }
14             }
15         }
16         return C[0] - 1;
17     }
18 }

View Code