|
解題關(guān)鍵： 理解結(jié)構(gòu)特征,，抽象出狀態(tài)，寫(xiě)成狀態(tài)轉(zhuǎn)移方程。
動(dòng)態(tài)規(guī)劃理念：
1.最優(yōu)化原理
2.問(wèn)題求解模式
3.實(shí)現(xiàn) 動(dòng)態(tài)規(guī)劃經(jīng)典例題：
1.三角形找一條從頂?shù)降椎淖钚÷窂?/span> 分析 設(shè)狀態(tài)為 f (i; j )，表示從從位置 (i; j ) 出發(fā),，路徑的最小和,，則狀態(tài)轉(zhuǎn)移方程為 f(i,j)=min{f(i+1,j),f(i+1,j+1)}+(i,j)
2.最大子數(shù)組和 設(shè)狀態(tài)為 f[j]，表示以 S[j] 結(jié)尾的最大連續(xù)子序列和,，狀態(tài)轉(zhuǎn)移方程如下： f=max(f+A[i],A[i]);//對(duì)于數(shù)組里的一個(gè)整數(shù),，它只有兩種 選擇：1、加入之前的 SubArray,；2. 自己另起一個(gè) SubArray,。 maxsum=max(maxsum,f);// 求字串中最大的
3.回文最小劃分次數(shù) 對(duì)輸入的字符串劃分為一組回文字符串,最小的分割次數(shù) 所以要轉(zhuǎn)換成一維 DP。如果每次，從 i 往右掃描,，每找到一個(gè)回文就算一次 DP 的話,，就可以 轉(zhuǎn)換為 f(i)= 區(qū)間 [i, n-1] 之間最小的 cut 數(shù)，n 為字符串長(zhǎng)度,，則狀態(tài)轉(zhuǎn)移方程為
4.最佳時(shí)間買(mǎi)賣(mài)股票 設(shè)狀態(tài)f(i)表示區(qū)間[0,i-1]上的最大利潤(rùn),設(shè)置狀態(tài)g(i),，表示區(qū)間[i,n-1]上最大利潤(rùn)。 則最大利潤(rùn)為max{f(i)+g(i)};允許在一天內(nèi)買(mǎi)進(jìn)又賣(mài)出,，相當(dāng)于不交易,，因?yàn)轭}目的規(guī)定是最多兩次，而不是一定要兩次
5. 判斷字符串s3是否由s1,s2交叉存取組成 設(shè)狀態(tài) f[i][j],，表示 s1[0,i] 和 s2[0,j],，匹配 s3[0, i+j]。如果 s1 的最后一個(gè)字符等 于 s3 的最后一個(gè)字符,，則 f[i][j]=f[i-1][j],； 如果 s2 的最后一個(gè)字符等于 s3 的最后一個(gè)字符， 則 f[i][j]=f[i][j-1],。 因此狀態(tài)轉(zhuǎn)移方程如下： f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);
6.給定一個(gè)矩形表格，求從頂?shù)降椎淖钚『?/span> Minimum Path Sum 設(shè)狀態(tài)為 f[i][j],，表示從起點(diǎn) (0; 0) 到達(dá) (i; j ) 的最小路徑和,，則狀態(tài)轉(zhuǎn)移方程為： f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j]
7.使兩個(gè)字符串相等，最小的編輯次數(shù) Edit Distance 設(shè)狀態(tài)為 f[i][j],，表示 A[0,i] 和 B[0,j] 之間的最小編輯距離,。設(shè) A[0,i] 的形式是 str1c，B[0,j] 的形式是 str2d,， 1. 如果 c==d,，則 f[i][j]=f[i-1][j-1]； 2. 如果 c!=d,， (a) 如果將 c 替換成 d,，則 f[i][j]=f[i-1][j-1]+1； (b) 如果在 c 后面添加一個(gè) d,，則 f[i][j]=f[i][j-1]+1,； (c) 如果將 c 刪除，則 f[i][j]=f[i-1][j]+1,；
8.給定一串?dāng)?shù)字,，1對(duì)應(yīng)A，2對(duì)應(yīng)B,26對(duì)應(yīng)Z,，求有多少種解碼方式 Decode Ways 和爬樓梯問(wèn)題一樣, 設(shè) f (n) 表示爬 n 階樓梯的不同方法數(shù),，為了爬到第 n 階樓梯，有兩個(gè)選擇： · 從第 n-1 階前進(jìn) 1 步； · 從第 n-2 階前進(jìn) 2 步,； 因此,，有 f (n) = f (n-1) + f (n-2)。 這是一個(gè)斐波那契數(shù)列,。
9. 不同的子序列Distinct Subsequences 給定2個(gè)字符串a, b,，求b在a中出現(xiàn)的次數(shù)。要求可以是不連續(xù)的,，但是b在a中的順序必須和b以前的一致,。 Here is an example: S = "rabbbit", T = "rabbit" Return 3.
類似于數(shù)字分解的題目。dp[i][j]表示：b的前j個(gè)字符在a的前i個(gè)字符中出現(xiàn)的次數(shù),。
如果S[i]==T[j],，那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。 意思是：如果當(dāng)前S[i]==T[j],，那么當(dāng)前這個(gè)字母即可以保留也可以拋棄,，所以變換方法等于保留這個(gè)字母的變換方法加上不用這個(gè)字母的變換方法。 意思是如果當(dāng)前字符不等，那么就只能拋棄當(dāng)前這個(gè)字符 遞歸公式中用到的dp[0][0] = 1,，dp[i][0] = 0（把任意一個(gè)字符串變換為一個(gè)空串只有一個(gè)方法
10.單詞分解Word Break 字符串是否可以分解為給定的單詞 For example, given s = "leetcode", dict = ["leet", "code"]. dp[i] 表示源串的前i個(gè)字符可以滿足分割,，那么 dp[ j ] 滿足分割的條件是存在k 使得 dp [k] && substr[k,j]在字典里。
真題：
1.Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is
Note:
分析
設(shè)狀態(tài)為 f (i; j ),，表示從從位置 (i; j ) 出發(fā),，路徑的最小和，則狀態(tài)轉(zhuǎn)移方程為
f(i,j)=min{f(i+1,j),f(i+1,j+1)}+(i,j)
代碼
// LeetCode, Triangle
// 時(shí)間復(fù)雜度 O(n^2),，空間復(fù)雜度 O(1)
class Solution {
public:
int minimumTotal (vector<vector<int>>& triangle)
{
for (int i = triangle.size() - 2; i >= 0; --i)
{
for (int j = 0; j < i + 1; ++j)
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
return triangle [0][0];
};
2.Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
自己最初想法：
需找最大字串的起點(diǎn)和終點(diǎn),。不是特別好解
答案：把原字符串分成很多不同的字串，然后求出字串中最大的,。
設(shè)狀態(tài)為 f[j],，表示以 S[j] 結(jié)尾的最大連續(xù)子序列和，狀態(tài)轉(zhuǎn)移方程如下： f=max(f+A[i],A[i]);//對(duì)于數(shù)組里的一個(gè)整數(shù),，它只有兩種 選擇：1,、加入之前的 SubArray；2. 自己另起一個(gè) SubArray,。 maxsum=max(maxsum,f);// 求字串中最大的 代碼： class Solution { public: int maxSubArray(int A[], int n) { if(0==n) return 0; int f=0;//f[j],，表示以 A[j] 結(jié)尾的最大連續(xù)子序列和 int maxsum=A[0]; for(int i=0;i<n;++i) {
f=max(f+A[i],A[i]);//是否需要另起一個(gè)字串,如果之前的對(duì)我沒(méi)貢獻(xiàn),，還不如另起一個(gè)字串。 maxsum=max(maxsum,f); //字串中最大的 } return maxsum; } };
3.Palindrome Partitioning II 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 = 題意分析： 對(duì)輸入的字符串劃分為一組回文字符串,最小的分割次數(shù)
分析
定義狀態(tài) f(i,j) 表示區(qū)間 [i,j] 之間最小的 cut 數(shù),，則狀態(tài)轉(zhuǎn)移方程為
這是一個(gè)二維函數(shù),，實(shí)際寫(xiě)代碼比較麻煩。 所以要轉(zhuǎn)換成一維 DP,。如果每次,，從 i 往右掃描，每找到一個(gè)回文就算一次 DP 的話,，就可以 轉(zhuǎn)換為 f(i)= 區(qū)間 [i, n-1] 之間最小的 cut 數(shù),，n 為字符串長(zhǎng)度，則狀態(tài)轉(zhuǎn)移方程為
一個(gè)問(wèn)題出現(xiàn)了,，就是如何判斷 [i,j] 是否是回文,？每次都從 i 到 j 比較一遍？太浪費(fèi)了,，這 里也是一個(gè) DP 問(wèn)題,。 定義狀態(tài) P[i][j] = true if [i,j] 為回文，那么 P[i][j] = str[i] == str[j] && P[i+1][j-1]
代碼
// LeetCode, Palindrome Partitioning II // 時(shí)間復(fù)雜度 O(n^2),，空間復(fù)雜度 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; // 最后一個(gè) 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.Maximal Rectangle 描述 Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. 題目就是給一個(gè)矩陣,，找一個(gè)全是一的最大子矩陣。
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
分析： 設(shè)狀態(tài)f(i)表示區(qū)間[0,i-1]上的最大利潤(rùn),設(shè)置狀態(tài)g(i),，表示區(qū)間[i,n-1]上最大利潤(rùn),。 則最大利潤(rùn)為max{f(i)+g(i)};允許在一天內(nèi)買(mǎi)進(jìn)又賣(mài)出，相當(dāng)于不交易,，因?yàn)轭}目的規(guī)定是最多兩次，而不是一定要兩次,。 代碼 // LeetCode, Best Time to Buy and Sell Stock III // 時(shí)間復(fù)雜度 O(n),，空間復(fù)雜度 O(n) class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() < 2) return 0; const int n = prices.size(); vector<int> f(n, 0); vector<int> g(n, 0); for (int i = 1, valley = prices[0]; i < n; ++i) { valley = min(valley, prices[i]); f[i] = max(f[i - 1], prices[i] - valley); } for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) { peak = max(peak, prices[i]); g[i] = max(g[i], peak - prices[i]); } int max_profit = 0; for (int i = 0; i < n; ++i) max_profit = max(max_profit, f[i] + g[i]); return max_profit; } };
6.Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
When s3 = 分析：判斷字符串s3是否由s1,s2交叉存取組成
設(shè)狀態(tài) f[i][j]，表示 s1[0,i] 和 s2[0,j],，匹配 s3[0, i+j],。如果 s1 的最后一個(gè)字符等 于 s3 的最后一個(gè)字符，則 f[i][j]=f[i-1][j],； 如果 s2 的最后一個(gè)字符等于 s3 的最后一個(gè)字符,， 則 f[i][j]=f[i][j-1]。 因此狀態(tài)轉(zhuǎn)移方程如下： f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]); 1 class Solution { 2 private: 3 bool f[1000][1000]; 4 public: 5 bool isInterleave(string s1, string s2, string s3) { 6 // Start typing your C/C++ solution below 7 // DO NOT write int main() function 8 if (s1.size() + s2.size() != s3.size()) 9 return false; 10 11 f[0][0] = true; 12 for(int i = 1; i <= s1.size(); i++) 13 f[i][0] = f[i-1][0] && (s3[i-1] == s1[i-1]); 14 15 for(int j = 1; j <= s2.size(); j++) 16 f[0][j] = f[0][j-1] && (s3[j-1] == s2[j-1]); 17 18 for(int i = 1; i <= s1.size(); i++) 19 for(int j = 1; j <= s2.size(); j++) 20 f[i][j] = (f[i][j-1] && s2[j-1] == s3[i+j-1]) || (f[i-1][j] && s1[i-1] == s3[i+j-1]); 21 22 return f[s1.size()][s2.size()]; 23 } 24 };
動(dòng)規(guī) + 滾動(dòng)數(shù)組 // LeetCode, Interleaving String // 二維動(dòng)規(guī) + 滾動(dòng)數(shù)組,，時(shí)間復(fù)雜度 O(n^2),，空間復(fù)雜度 O(n) class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.length() + s2.length() != s3.length()) return false; if (s1.length() < s2.length()) return isInterleave(s2, s1, s3); vector<bool> f(s2.length() + 1, true); for (size_t i = 1; i <= s2.length(); ++i) f[i] = s2[i - 1] == s3[i - 1] && f[i - 1]; for (size_t i = 1; i <= s1.length(); ++i) { f[0] = s1[i - 1] == s3[i - 1] && f[0]; for (size_t j = 1; j <= s2.length(); ++j) f[j] = (s1[i - 1] == s3[i + j - 1] && f[j]) || (s2[j - 1] == s3[i + j - 1] && f[j - 1]); } return f[s2.length()]; } };
7.Scramble String(混雜字符串) Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = great
/ gr eat
/ \ / g r e at
/ a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node rgeat
/ rg eat
/ \ / r g e at
/ a t
We say that
Similarly, if we continue to swap the children of nodes rgtae
/ rg tae
/ \ / r g ta e
/ t a
We say that Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
8.Minimum Path Sum 描述 Given a m n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time 分析： 設(shè)狀態(tài)為 f[i][j]，表示從起點(diǎn) (0; 0) 到達(dá) (i; j ) 的最小路徑和,，則狀態(tài)轉(zhuǎn)移方程為： f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j]
代碼： 備忘錄法 // LeetCode, Minimum Path Sum // 備忘錄法 class Solution { public: int minPathSum(vector<vector<int> > &grid) { const int m = grid.size(); const int n = grid[0].size(); this->f = vector<vector<int> >(m, vector<int>(n, -1)); return dfs(grid, m-1, n-1); } private: vector<vector<int> > f; // 緩存 int dfs(const vector<vector<int> > &grid, int x, int y) { if (x < 0 || y < 0) return INT_MAX; // 越界,，終止條件,，注意，不是 0 if (x == 0 && y == 0) return grid[0][0]; // 回到起點(diǎn),，收斂條件 return min(getOrUpdate(grid, x - 1, y), getOrUpdate(grid, x, y - 1)) + grid[x][y]; } int getOrUpdate(const vector<vector<int> > &grid, int x, int y) { if (x < 0 || y < 0) return INT_MAX; // 越界,，注意，不是 0 if (f[x][y] >= 0) return f[x][y]; else return f[x][y] = dfs(grid, x, y); } }; 動(dòng)規(guī) // LeetCode, Minimum Path Sum // 二維動(dòng)規(guī) class Solution { public: int minPathSum(vector<vector<int> > &grid) { if (grid.size() == 0) return 0; const int m = grid.size(); const int n = grid[0].size(); int f[m][n]; f[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (int i = 1; i < n; i++) { f[0][i] = f[0][i - 1] + grid[0][i]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } return f[m - 1][n - 1]; } }; 動(dòng)規(guī) + 滾動(dòng)數(shù)組 // LeetCode, Minimum Path Sum // 二維動(dòng)規(guī) + 滾動(dòng)數(shù)組 class Solution { public: int minPathSum(vector<vector<int> > &grid) { const int m = grid.size(); const int n = grid[0].size(); int f[n]; fill(f, f+n, INT_MAX); // 初始值是 INT_MAX,，因?yàn)楹竺嬗昧?min 函數(shù),。 f[0] = 0; for (int i = 0; i < m; i++) { f[0] += grid[i][0]; for (int j = 1; j < n; j++) { // 左邊的 f[j]，表示更新后的 f[j],，與公式中的 f[i[[j] 對(duì)應(yīng) // 右邊的 f[j],，表示老的 f[j]，與公式中的 f[i-1][j] 對(duì)應(yīng) f[j] = min(f[j - 1], f[j]) + grid[i][j]; } } return f[n - 1]; } };
描述 Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: · Insert a character · Delete a character · Replace a character
分析 設(shè)狀態(tài)為 f[i][j],，表示 A[0,i] 和 B[0,j] 之間的最小編輯距離,。設(shè) A[0,i] 的形式是 str1c，B[0,j] 的形式是 str2d,， 1. 如果 c==d,，則 f[i][j]=f[i-1][j-1]； 2. 如果 c!=d,， (a) 如果將 c 替換成 d,，則 f[i][j]=f[i-1][j-1]+1； (b) 如果在 c 后面添加一個(gè) d,，則 f[i][j]=f[i][j-1]+1,； (c) 如果將 c 刪除，則 f[i][j]=f[i-1][j]+1,； 動(dòng)規(guī) // LeetCode, Edit Distance // 二維動(dòng)規(guī),，時(shí)間復(fù)雜度 O(n*m)，空間復(fù)雜度 O(n*m) class Solution { public: int minDistance(const string &word1, const string &word2) { const size_t n = word1.size(); const size_t m = word2.size(); // 長(zhǎng)度為 n 的字符串,，有 n+1 個(gè)隔板 int f[n + 1][m + 1]; for (size_t i = 0; i <= n; i++) f[i][0] = i; for (size_t j = 0; j <= m; j++) f[0][j] = j; for (size_t i = 1; i <= n; i++) { for (size_t j = 1; j <= m; j++) { if (word1[i - 1] == word2[j - 1]) f[i][j] = f[i - 1][j - 1]; else { int mn = min(f[i - 1][j], f[i][j - 1]); f[i][j] = 1 + min(f[i - 1][j - 1], mn); } } } return f[n][m]; } };
動(dòng)規(guī) + 滾動(dòng)數(shù)組 // LeetCode, Edit Distance // 二維動(dòng)規(guī) + 滾動(dòng)數(shù)組 // 時(shí)間復(fù)雜度 O(n*m),，空間復(fù)雜度 O(n) class Solution { public: int minDistance(const string &word1, const string &word2) { if (word1.length() < word2.length()) return minDistance(word2, word1); int f[word2.length() + 1]; int upper_left = 0; // 額外用一個(gè)變量記錄 f[i-1][j-1] for (size_t i = 0; i <= word2.size(); ++i) f[i] = i; for (size_t i = 1; i <= word1.size(); ++i) { upper_left = f[0]; f[0] = i; for (size_t j = 1; j <= word2.size(); ++j) { int upper = f[j]; if (word1[i - 1] == word2[j - 1]) f[j] = upper_left; else f[j] = 1 + min(upper_left, min(f[j], f[j - 1])); upper_left = upper; } } return f[word2.length()]; } };
10 Decode Ways 描述 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2
分析 : 和爬樓梯問(wèn)題一樣, 設(shè) f (n) 表示爬 n 階樓梯的不同方法數(shù)，為了爬到第 n 階樓梯,，有兩個(gè)選擇： · 從第 n-1 階前進(jìn) 1 步,； · 從第 n-2 階前進(jìn) 2 步； 因此,，有 f (n) = f (n-1) + f (n-2),。 這是一個(gè)斐波那契數(shù)列。
這里也一樣,，多一些約束條件而已,。判斷兩個(gè)數(shù)字時(shí)，是否小于26 代碼 // LeetCode, Decode Ways // 動(dòng)規(guī),，時(shí)間復(fù)雜度 O(n),，空間復(fù)雜度 O(1)+滾動(dòng)數(shù)組 class Solution { public: int numDecodings(const string &s) { if (s.empty() || s[0] == '0') return 0; int prev = 0;//f(0)=0 int cur = 1;//f(1)=1 // 長(zhǎng)度為 n 的字符串,，有 n+1 個(gè)階梯 for (size_t i = 1; i <= s.size(); ++i) { if (s[i-1] == '0') cur = 0; if (i < 2 || !(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) prev = 0; int tmp = cur; cur = prev + cur;//f(i)=f(i-2)+f(i-1) prev = tmp; } return cur; } };
11 Distinct Subsequences（不同的子序列）
描述
Given a string S and a string T , count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE"
is a subsequence of "ABCDE" while "AEC" is not).
Here is an example: S = "rabbbit", T = "rabbit"
Return 3.
分析 類似于數(shù)字分解的題目,。dp[i][j]表示：b的前j個(gè)字符在a的前i個(gè)字符中出現(xiàn)的次數(shù),。
意思是：如果當(dāng)前a[i]==b[j],，那么當(dāng)前這個(gè)字母即可以保留也可以拋棄，所以變換方法等于保留這個(gè)字母的變換方法加上不用這個(gè)字母的變換方法,。
如果a[i]!=b[i],，那么dp[i][j] = dp[i-1][j]，
意思是如果當(dāng)前字符不等,，那么就只能拋棄當(dāng)前這個(gè)字符
遞歸公式中用到的dp[0][0] = 1,，dp[i][0] = 0（把任意一個(gè)字符串變換為一個(gè)空串只有一個(gè)方法
12 Word Break
代碼 // LeetCode, Distinct Subsequences // 二維動(dòng)規(guī) + 滾動(dòng)數(shù)組 // 時(shí)間復(fù)雜度 O(m*n)，空間復(fù)雜度 O(n) class Solution { public: int numDistinct(const string &S, const string &T) { vector<int> f(T.size() + 1); f[0] = 1; for (int i = 0; i < S.size(); ++i) { for (int j = T.size() - 1; j >= 0; --j) { f[j + 1] += S[i] == T[j] ? f[j] : 0; } } return f[T.size()]; } };
描述 Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".
分析：
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
For example, given
A solution is 跟第一題一樣，就是要返回所有可能的切分,， 做切分反應(yīng)是用回溯,，但是不剪枝肯定要超時(shí)。 這里用了一個(gè)math[i][j] 來(lái)表示 i--j 這一段是否可以切分,，然后在dfs的時(shí)候利用看最后剩余的子串能否切分來(lái)剪枝
|
|
|
來(lái)自： dinghj > 《基礎(chǔ)-算法》
