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 };
?C#

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 }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
