网站开发数据库,卫生局网站建设,百度小程序如何做网站,程序员编程培训题目一, 题目二 思路 1. 第一遍做时就参考别人的, 现在又忘记了 做的时候使用的是二维动态规划, 超时加超内存 2. 只当 string 左部分是回文的时候才有可能减少 cut 3. 一维动规. 令 cuts[i] 表示string[i, string.size()] 所需的切割数, 那么 状态转移方程为 cuts[i] min(cut… 题目一, 题目二 思路 1. 第一遍做时就参考别人的, 现在又忘记了 做的时候使用的是二维动态规划, 超时加超内存 2. 只当 string 左部分是回文的时候才有可能减少 cut 3. 一维动规. 令 cuts[i] 表示string[i, string.size()] 所需的切割数, 那么 状态转移方程为 cuts[i] min(cuts[j]1) j i string[i, j] is palindrome 时间复杂度上仍是 o(n*n), 但更新 cuts 的限制条件比较多了, cuts[i] 更新频率较低 代码: 超时二维动规代码 #include iostream
#include memory.h
using namespace std;int cuts[1000][1000];
int palindrom[1000][1000];
const int INFS 0x3f3f3f3f;
class Solution {
public:int minCut(string s) {memset(cuts, 0x3f, sizeof(cuts));memset(palindrom, 0x3f, sizeof(palindrom));int curcuts countCuts(s,0,s.size()-1);return curcuts;}int countCuts(string s, int i, int j) {if(j i) return 0;if(isPalindrome(s,i,j))return (cuts[i][j]0);if(cuts[i][j] ! INFS)return cuts[i][j];int curcuts INFS;for(int k i; k j; k) {curcuts min(curcuts, 1countCuts(s,i,k)countCuts(s,k1,j));}return (cuts[i][j]curcuts);}bool isPalindrome(string s, int i, int j) {if(palindrom[i][j] 1)return true;if(j i)return (palindrom[i][j] true);if(palindrom[i][j] 0)return false;return (palindrom[i][j] (s[i]s[j] isPalindrome(s,i1,j-1)));}
};int main() {string str apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp;cout str.size() endl;cout (new Solution())-minCut(str) endl;return 0;
}优化后的一维动规 #include iostream
#include memory.h
using namespace std;int cuts[1500];
int palindrom[1500][1500];
const int INFS 0x3f3f3f3f;
class Solution {
public:int minCut(string s) {memset(cuts, 0x3f, sizeof(cuts));memset(palindrom, 0x3f, sizeof(palindrom));int curcuts countCuts(s,0,s.size()-1);return curcuts;}int countCuts(string s, int i, int j) {if(j i) return 0;if(isPalindrome(s,i,j))return 0;if(cuts[i] ! INFS)return cuts[i];int curcuts INFS;for(int k i; k j; k) {if(isPalindrome(s,i,k))curcuts min(curcuts, 1countCuts(s,k1,j));}return (cuts[i]curcuts);}bool isPalindrome(string s, int i, int j) {if(palindrom[i][j] 1)return true;if(j i)return (palindrom[i][j] true);if(palindrom[i][j] 0)return false;return (palindrom[i][j] (s[i]s[j] isPalindrome(s,i1,j-1)));}
};int main() {string str bb;cout str.size() endl;cout (new Solution())-minCut(str) endl;return 0;
}I 第一题用动态规划也是可以做的, 不过会比较麻烦(与Word Break类似) 这里用 dfs 加打印路径, 比较直观 int palindrom[1500][1500];
vectorvectorstring res;
class Solution {
public:vectorvectorstring partition(string s) {res.clear();memset(palindrom, 0x3f, sizeof(palindrom));vectorstring tmp;dfs(s, tmp, 0);return res;}bool isPalindrome(string s, int i, int j) {if(palindrom[i][j] 1)return true;if(j i)return (palindrom[i][j] true);if(palindrom[i][j] 0)return false;return (palindrom[i][j] (s[i]s[j] isPalindrome(s,i1,j-1)));}void dfs(string s, vectorstring cur_vec, int depth) {if(depth s.size()) {res.push_back(cur_vec);return;}for(int i depth; i s.size(); i ) {if(isPalindrome(s, depth,i)) {cur_vec.push_back(s.substr(depth,i-depth1));dfs(s, cur_vec, i1);cur_vec.pop_back();}}}
};
