LeetCode 之 Palindrome Partitioning II（动态规划）

灰太狼 2022-08-03 08:21 166阅读 0赞

【问题描述】

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = `"aab"`,

Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.

1.【基础知识】

1）substr函数掌握模糊；

2）动规与贪心算法的回顾；

3）树的深搜和广搜的应用能力；

4）fill\_n函数。

2.【屌丝代码】

卡壳的地方：

1.剩下一个元素可以不切，直接判定跳出（已解决）；

2.动规，一次循环同时进行前向与后向回文判定，并且采用初次前削判定和初次后削判定（已解决）；

3.贪心，每次都比较，得到当下可以最快回文的长度，只不过未能实现（已解决）；

4.解决了全部短小用例，倒在了代码中那段长不拉几的字符串用例上；

5.屌丝算法思想：

1）前向搜索：

1.1）先检查去掉最后Num个元素是不是回文；

1.1.1）是，则判断余下的是不是回文串——不是则直接进入下一层循环，是则直接跳出循环；

1.1.2）不是，继续循环体；

1.2）检查去掉最前Num个元素是不是回文；

1.2.1）是，则判断余下的是不是回文串——不是则直接进入下一层循环，是则直接跳出循环；

1.2.2）不是，继续循环体；

1.3）Num++

1.4）得到最终count\_a;

2）后向搜索：

将1.1与1.2调换执行,得到最终count\_b；

3）比较count\_a与count\_b，返回最小值。

#include <vector>  
    #include <iostream>
    #include <algorithm> 
    #include <vector>
    #include <string>
    
    using namespace std; 
    
    class Solution {
    public:
        int minCut(string s) 
    	{
    		int len = s.length();
    		if(len<=1||IsPld(s)) 
    			return 0;
    
    		int tmp_len(len),cot_a(0),cot_b(0);
    		string tmp_str = s;
    		
    		/*
    		for(i=len-1;i>0;i--) // 切几刀？ 如：0，表示不切，原字符串就是一个回文串
    		{
    			int *arr = (int*)malloc(sizeof(int)*(i+1));
    			arr[0] = 0;
    			vector<string> subs;
    			for(j=1;j<=i+1;j++) // 循环刀数
    				for(k>arr[j-1];k<) // 每一刀怎么切？ 下刀点
    				// 下一刀要比上一刀大；
    				// 第一刀不能比0小；第一刀不能大于串长减刀数；
    				// 第k刀不能比len-k大；
    				// 最后一刀不能比串长大；
    				{
    					s.substr
    				}
    			delete []arr;
    		}*/
    
    		/*
    		while(tmp_len)
    		{
    			if(IsPld(tmp_str.substr(0,tmp_len)))
    			{
    				cot_a++;
    				tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    			}
    			else 
    				if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
    				{
    					cot_a++;
    					tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
    					tmp_len = tmp_str.size();
    					if(IsPld(tmp_str))
    						break;
    				}
    				else
    				{
    					tmp_len--;
    				}
    		}
    		tmp_len = len;
    		tmp_str = s;		
    		while(tmp_len)
    		{
    			if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
    			{
    				cot_b++;
    				tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    			}
    			else 
    				if(IsPld(tmp_str.substr(0,tmp_len)))
    				{
    					cot_b++;
    					tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
    					tmp_len = tmp_str.size();
    					if(IsPld(tmp_str))
    						break;
    				}
    				else
    				{
    					tmp_len--;
    				}
    		}
    		return min(cot_a,cot_b);
    		*/
    		while(tmp_len)
    		{
    			if(IsPld(tmp_str.substr(0,tmp_len)))
    			{
    				cot_a++;
    				tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    			}
    			if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
    			{
    				cot_a++;
    				tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    			}
    				tmp_len--;
    		}
    		tmp_len = len;
    		tmp_str = s;
    		while(tmp_len)
    		{
    			if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
    			{
    				cot_b++;
    				tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    				continue;
    			}
    			if(IsPld(tmp_str.substr(0,tmp_len)))
    			{
    				cot_b++;
    				tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
    				tmp_len = tmp_str.size();
    				if(IsPld(tmp_str))
    					break;
    				continue;
    			}
    			tmp_len--;
    		}
    		return min(cot_b,cot_a);
        }
    	bool IsPld(string s)
    	{
    		if(s.length()<=1)
    			return true;
    		int i(0),j(s.size()-1);
    		while(i<j)
    		{
    			if(s[i]!=s[j])
    				return false;
    			i++;
    			j--;
    		}
    		return true;
    	}
    };
    
    int main()  
    {
    	string mystr = "adabdcaebdcebdcacaaaadbbcadabcbeabaadcbcaaddebdbddcbdacdbbaedbdaaecabdceddccbdeeddccdaabbabbdedaaabcdadbdabeacbeadbaddcbaacdbabcccbaceedbcccedbeecbccaecadccbdbdccbcbaacccbddcccbaedbacdbcaccdcaadcbaebebcceabbdcdeaabdbabadeaaaaedbdbcebcbddebccacacddebecabccbbdcbecbaeedcdacdcbdbebbacddddaabaedabbaaabaddcdaadcccdeebcabacdadbaacdccbeceddeebbbdbaaaaabaeecccaebdeabddacbedededebdebabdbcbdcbadbeeceecdcdbbdcbdbeeebcdcabdeeacabdeaedebbcaacdadaecbccbededceceabdcabdeabbcdecdedadcaebaababeedcaacdbdacbccdbcece";
    	cout<<mystr.substr(1,2)<<endl; // string.substr(首元素索引，子串长度)
    	Solution mySln;
    	int num = mySln.minCut(mystr);
    	cout<<num<<endl;
    	while(1);
        return 0; 
    }

3.【源码AC】

// LeetCode, Palindrome Partitioning II
    // 时间复杂度 O(n^2)，空间复杂度 O(n^2)
    class Solution {
    public:
        int minCut(string s) {
            const int n = s.size();
            int f[n+1];
            bool p[n][n];
            fill_n(&p[0][0], n * n, false);
            //the worst case is cutting by each char
            for (int i = 0; i <= n; i++)
            f[i] = n - 1 - i; // 最后一个 f[n]=-1
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) {
                        p[i][j] = true;
                        f[i] = min(f[i], f[j + 1] + 1);
                    }
                }
            }
        return f[0];
        }
    };

4.【复盘】

1）卡壳部分

*  不能解决的原因在于字符串太长，耗时也在1H以上，题目未解出来；
 *  动规的数学式子未能很好定义提炼。

2）AC源码思想——动态规划

定义状态 f(i,j) 表示区间 \[i,j\] 之间最小的 cut 数，则状态转移方程为  
f(i, j) = min \{f(i, k) + f(k + 1, j)\} , i ≤ k ≤ j,0 ≤ i ≤ j < n  
这是一个二维函数，实际写代码比较麻烦。所以要转换成一维 DP。如果每次，从 i 往右扫描，每找到一个回文就算一次 DP 的话，就可以转换为

f(i) = 区间 \[i, n-1\] 之间最小的 cut 数

n 为字符串长度，则状态转移方程为  
f(i) = min \{f(j + 1) + 1\} , i ≤ j < n  
一个问题出现了，就是如何判断 \[i,j\] 是否是回文？每次都从 i 到 j 比较一遍？太浪费了，这里也是一个 DP 问题。  
定义状态 P\[i\]\[j\] = true if \[i,j\] 为回文 ，那么

P\[i\]\[j\] = ( str\[i\] == str\[j\] && P\[i+1\]\[j-1\] )