专题6--动态规划
1、动态规划基础知识
什么情况下可能是动态规划？满足下面三个条件之一:
1. Maximum/Minimum -- 最大最小，最长，最短；写程序一般有max/min。
2. Yes/No----是否可行；写程序一般有||。
3. Count(*)--数方案的个数，比如有多少条路径这种。初始化0个的情况下，初始化为1，联想组合数学里面0! = 1。
则 “极有可能”是使用动态规划求解。
什么情况下可能不是动态规划？
1）如果题目需要求出所有 “具体 ”的方案而非方案 “个数 ”；
2）输入数据是一个 “集合 ”而不是 “序列 ”。（区分就是调整元素顺序看是否对求解有影响）
动态规划的4点要素：
1） 状态 State
灵感，创造力，存储小规模问题的结果
a) 最优解/Maximum/Minimum
b) Yes/No
c) Count(*)
2） 方程 Function
状态之间的联系，怎么通过小的状态，来求得大的状态
3） 初始化 Intialization
最极限的小状态是什么, 起点
4） 答案 Answer
最大的那个状态是什么，终点
动态规划有四类：
1. Matrix DP (15%)
2. Sequence (40%)
3. Two Sequences DP (40%)
*4. Others (5%)
动态规划就是 *解决了重复计算 * 的搜索。
动态规划的实现方式：
1. 记忆化搜索；
2. 循环。
循环求解更 *正规 *，存在空间优化的可能，大多数面试官可以接受;（滚动数组）
记忆化搜索空间耗费更大，但思维难度小，编程难度小，时间效率很多情况下更高，少数有 *水平 *的面试官可以接受。
动态规划时间复杂度分析就是看有几个for循环。
3、Matrix DP
state: f[x][y] 表示我从起点走到坐标 x,y……
function: 研究走到 x,y这 个点之前的一步
intialize: 起点
answer: 终点
小技巧：intialize: f[0][0] = A[0][0]
// f[i][0] = sum(0,0 -> i,0)
// f[0][i] = sum(0,0 -> 0,i)
初始化的时候需要初始化f[i][0] ，f[0][i] ，这样可以在i-1的时候避免边界检查。
3.1、120. Triangle
https://leetcode.com/problems/triangle/#/description
找到和最小的一条路径。
思路：
1）记忆化搜索memorize+ divide and conquer
class Solution { public: int helper(int x,int y,int size,vector<vector<int>>& triangle,vector<vector<int>>& minSum){ if(x >= size){ return 0; } if(minSum[x][y] != INT_MAX){ return minSum[x][y]; }minSum[x][y] </span>= min(helper(x + <span style="color: #800080;">1</span><span style="color: #000000;">,y, size,triangle,minSum), helper(x </span>+ <span style="color: #800080;">1</span>,y + <span style="color: #800080;">1</span><span style="color: #000000;">,size,triangle,minSum)) </span>+<span style="color: #000000;"> triangle[x][y]; </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> minSum[x][y]; } </span><span style="color: #0000ff;">int</span> minimumTotal(vector<vector<<span style="color: #0000ff;">int</span>>>&<span style="color: #000000;"> triangle) { </span><span style="color: #0000ff;">if</span>(triangle.size() == <span style="color: #800080;">0</span> || triangle[<span style="color: #800080;">0</span>].size() == <span style="color: #800080;">0</span><span style="color: #000000;">){ </span><span style="color: #0000ff;">return</span> -<span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">int</span> row =<span style="color: #000000;"> triangle.size(); </span><span style="color: #0000ff;">int</span> col = triangle[row - <span style="color: #800080;">1</span><span style="color: #000000;">].size(); vector</span><vector<<span style="color: #0000ff;">int</span>>> minSum(row,vector<<span style="color: #0000ff;">int</span>><span style="color: #000000;"> (col,INT_MAX)); </span><span style="color: #0000ff;">return</span> helper(<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span><span style="color: #000000;">,triangle.size(),triangle,minSum); }};
不管是二叉树还是其他这种树结构的，都是递归到叶子节点的下一个空节点再返回，这点可以节省很多思考过程，很好用。
if(x == size){ return 0; }
所谓记忆化搜索就是指用一个数组存储之前的状态，首先初始化数组全为INT_MAX，计算之前先看看是否计算过，计算过就直接返回。
if(minSum[x][y] != INT_MAX){ return minSum[x][y]; }
2）动态规划：
使用动态规划四步走方法，状态代表 state: f[x][y] = minimum path value from x,y to bottom，initialization：初始化最后一行，function：当前和等于当前值加上下一行的最小值，return：f[0][0]。
class Solution { public: //bottom to top int minimumTotal(vector<vector<int>>& triangle) { // state: f[x][y] = minimum path value from x,y to bottom int col = triangle.size(); int row = triangle[col - 1].size(); vector<vector<int>> f(col,vector<int> (row,0));//f[i][j]代表从下到(i,j)位置的最小和 //initial for(int i = 0;i< row;++i){ f[col - 1][i] = triangle[col - 1][i]; } //function，bottom to top for(int i = col - 2;i >= 0;--i){ for(int j = 0;j < row;++j){ f[i][j] = triangle[i][j] + min(f[i + 1][j],f[i + 1][j + 1]); } } //result return f[0][0]; } };
3.2 64. Minimum Path Sum
https://leetcode.com/problems/minimum-path-sum/tabs/description
思路：题目意思是从左上走到右下。和上面那题差不多。注意初始化第一行和第一列，然后function的时候从第二列和第二行开始，避免了 i-1 的边界检查。
class Solution { public: int minPathSum(vector<vector<int>>& grid) { if(grid.size() == 0 || grid[0].size() == 0){ return -1; } int m = grid.size(); int n = grid[0].size(); //state vector<vector<int>> sum(m,vector<int> (n,0)); //intialization sum[0][0] = grid[0][0]; for(int i = 1;i < n;++i){ sum[0][i] = sum[0][i - 1] + grid[0][i]; } for(int i = 1;i < m;++i){ sum[i][0] = sum[i - 1][0] + grid[i][0]; } //function for(int i = 1;i < m;++i){ for(int j = 1;j < n;++j){ sum[i][j] = min(sum[i - 1][j],sum[i][j - 1]) + grid[i][j]; } } //result return sum[m - 1][n - 1]; } };
3.3 62. Unique Paths
https://leetcode.com/problems/unique-paths/tabs/description
机器人从左上走到右下有多少条路径。
思路：按照动态规划四步走策略，num[i][j]代表从起点到(i,j)这点路径之和；矩阵型动态规划初始化第一行和第一列，都为1；function等于top和left的路径之和；
结果返回num[m - 1][n - 1].
class Solution { public: int uniquePaths(int m, int n) { if(m == 0 || n == 0){ return -1; } //state vector<vector<int>> num(m,vector<int> (n,0)); //initialation num[0][0] = 1; for(int i =0;i < n;++i){ num[0][i] = 1; } for(int j =0;j < m;++j){ num[j][0] = 1; } //function for(int i = 1;i < m;++i){ for(int j = 1;j < n;++j){ num[i][j] = num[i - 1][j] + num[i][j - 1]; } } //result return num[m - 1][n - 1]; } };
3.4 63. Unique Paths II
https://leetcode.com/problems/unique-paths-ii/tabs/description/
机器人从左上走到右下有多少条路径。有障碍物的情况。
思路：这题和上题不同点在于有障碍物，对num[i][j]进行计算前要判断当前格子的值是否为1，为1的话就num赋值为0，不然就等于top和left的num值之和。
记住小细节：第一行和第一列进行赋值的时候，要注意先判断不是1，就将num赋值为1，不然直接break退出循环，因为vector定义的时候就已经初始化为0；
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { //exception if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0){ return -1; } //state int m = obstacleGrid.size(); int n= obstacleGrid[0].size(); vector<vector<int>> num(m,vector<int> (n,0)); //initialation<span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < n;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">if</span>(obstacleGrid[<span style="color: #800080;">0</span>][i] != <span style="color: #800080;">1</span><span style="color: #000000;">){ num[</span><span style="color: #800080;">0</span>][i] = <span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ </span><span style="color: #0000ff;">break</span><span style="color: #000000;">; } } </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">0</span>;j < m;++<span style="color: #000000;">j){ </span><span style="color: #0000ff;">if</span>(obstacleGrid[j][<span style="color: #800080;">0</span>] != <span style="color: #800080;">1</span><span style="color: #000000;">){ num[j][</span><span style="color: #800080;">0</span>] = <span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ </span><span style="color: #0000ff;">break</span><span style="color: #000000;">; } } </span><span style="color: #008000;">//</span><span style="color: #008000;">function</span> <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>;i < m;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">1</span>;j < n;++<span style="color: #000000;">j){ </span><span style="color: #0000ff;">if</span>(obstacleGrid[i][j] == <span style="color: #800080;">1</span><span style="color: #000000;">){ num[i][j] </span>= <span style="color: #800080;">0</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ num[i][j] </span>= num[i][j - <span style="color: #800080;">1</span>] + num[i - <span style="color: #800080;">1</span><span style="color: #000000;">][j]; } } } </span><span style="color: #008000;">//</span><span style="color: #008000;">answer</span> <span style="color: #0000ff;">return</span> num[m - <span style="color: #800080;">1</span>][n - <span style="color: #800080;">1</span><span style="color: #000000;">]; }};
4 序列型动态规划sequence dynamic programming
state: f[i]表示 “ 前 i” 个位置 /数字 /字母 ,(以第 i个 为 ).以第i个元素结尾的最值..
function: f[i] = f[j] … j 是 i之前的一个位置
intialize: f[0]..
answer: f[n-1]..
处理字符串类型的题目并且涉及到前i个字符，我们一般讲数组多开一个f(n + 1)，数组大小是n + 1.
4.1 70. Climbing Stairs
https://leetcode.com/problems/climbing-stairs/tabs/description
思路：递归，循环，动态规划
大炮打小鸟：动态规划（这题属于count，计算方案个数，同时里面的数不能随意交换，是序列不是集合所以可以使用动态规划）
state: f[i]表示前 i个位置，跳到第 i个位置的方案
总 数
function: f[i] = f[i-1] + f[i-2]
intialize: f[0] = 1
answer: f[n]
class Solution { public: int climbStairs(int n) { //state vector<int> f(n + 1,0); //intialization f[0] = 1; f[1] = 1; //function for(int i = 2;i <= n;++i){ f[i] = f[i - 1] + f[i - 2]; } //answer return f[n]; } };
循环：
class Solution { public: int climbStairs(int n) { int a = 1; int b = 1; int c = 1; for(int i = 1;i < n;++i){ c = a + b; a = b; b = c; } return c; } };
4.2 55. Jump Game
https://leetcode.com/problems/jump-game/tabs/description
矩阵中的数字代表跳跃的步数，是否能够跳到最后一格。
思路：首先判断能否使用动态规划：1）属于YES/NO问题，2）元素是有序的不是集合 => 可以使用序列型动态规划
虽然动态规划超时，但是思路需要知道。
这题需要用到贪心算法，计算出整个序列所能达到的最大长度，只要最大长度大于数组的最后一个下标，就可以是true，
class Solution { public: bool canJump(vector<int>& nums) { if(nums.empty()){ return false; } int longest = nums[0] + 0; for(int i = 1;i < nums.size();++i){ if(i <= longest && i + nums[i] > longest){ longest = i + nums[i]; } } return longest >= nums.size() - 1; } };
4.3 45. Jump Game II
https://leetcode.com/problems/jump-game-ii/description/
数组中每个数字代表最大跳跃的步数，到达最后一个元素，最少需要多少步数。
思路：动态规划算法会超时，但是需要掌握。因为是最少跳跃步数，所以初始化为最大值INT_MAX；
state: f[i]代表我跳到这个位置最少需要几步
function: f[i] = MIN(f[j]+1, j < i && j能 够 跳到 i)，每次操作就是上次跳的最小步数加1；
initialize: f[0] = 0;
answer: f[n-1]
class Solution { public: //最少跳跃步数 int jump(vector<int>& nums) { if(nums.size() == 0){ return 0; } int n = nums.size(); vector<int> dp(n,INT_MAX); dp[0] = 0;//初始化了第一个就不需要计算了 int minStep; for(int i = 1;i < n;++i){ minStep = INT_MAX; for(int j = 0;j < i;++j){ if(dp[j] != INT_MAX && nums[j] + j >= i && dp[j] + 1 < minStep){ minStep = dp[j] + 1;} } dp[i] </span>=<span style="color: #000000;"> minStep; } </span><span style="color: #0000ff;">return</span> dp[n - <span style="color: #800080;">1</span><span style="color: #000000;">]; }};
//贪心算法我自己的理解版本
#一直对贪心不感冒#。。。。cur表示最远能覆盖到的地方。last表示已经覆盖的地方，ret表示步数，以[2,3,1,1,4]为例子；
1、初始化==>cur = 0;ret = 0;last = 0;
2、i= 0的时候==>cur = 2 + 0 = 2；ret = 0;last = 0;
3、i = 1的时候==>i > last,last需要更新为cur，即last = 2,同时cur = 1 + 3 = 4,因为last更新了一次，所以ret需要加1；
class Solution { public: int jump(vector<int>& nums) { if(nums.size() == 0){ return -1; } int len = nums.size(); vector<int> small(len,INT_MAX); //initalization small[0] = 0; //function for(int i = 1; i < len;++i){ for(int j = 0;j < i;++j){ if(small[j] != INT_MAX && j + nums[j] >= i){ small[i] = min(small[i],small[j] + 1); } } } //answer return small[len - 1];}};
贪心法：实验室小纸贴校外版参照
class Solution { public: int jump(vector<int>& nums) { if(nums.size() == 0){ return -1; } int len = nums.size(); int cur = 0; int last = 0; int step = 0; for(int i = 0;i < len;++i){ if(i > last){ last = cur; ++step; } cur = max(cur,i + nums[i]); } return step; } };
4.4 300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/description/
思路：f[i]代表num[i]结尾的最长序列，注意该题初始化的时候要全部初始化为1，不能只初始化f[0]，因为[3,2,4]这种情况，f[1]没有初始化就为0，导致计算错误。
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() == 0){ return 0; } //state int n = nums.size(); int maxNum = 1; vector<int> f(n,1);//must all are equal 1 //intialization // f[0] = 1; //function for(int i = 1;i < n;++i){ for(int j = 0;j < i;++j){ if(nums[j] < nums[i]){ f[i] = max(f[i],f[j] + 1); maxNum = max(maxNum,f[i]); } } } //answer return maxNum; } };
4.5 132. Palindrome Partitioning II
https://leetcode.com/problems/palindrome-partitioning-ii/description/
将一个字符串切割为回文串，求最小的切割次数。
思路：1)使用DFS
2）使用动态规划，传统的序列性动态规划，使用双指针方式判断回文的方法复杂度为n^3，超时了，所以使用两个动态规划，一个为区间型动态规划，序列性动态规划需要将数组多设一个，f(n + 1)，初始化需要全部初始化，并且将第0个初始化为-1，
**简化回文判断复杂度的区间型动态规划：先判断两端字符是否相等，然后利用数组判断中间部分是否相等。，使用len长度控制。
/////////////////////////////////////////////////////////////////////////////////////*********//////////////////////////////////////////////////
state: f[i]”前i”个字符组成的子字符串需要最少几次cut(最少能被分割为多少个字符串-1)
function: f[i] = MIN{f[j]+1}, j < i && j+1 ~ i这一段是一个回文串
intialize: f[i] = i - 1 (f[0] = -1)
answer: f[s.length()]
/////////////////////////////////////////////////////////////////////////////////////*********//////////////////////////////////////////////////
class Solution { public: vector<vector<bool>> isPalindrome(string s){ vector<vector<bool>> result(s.size(),vector<bool> (s.size(),false)); for(int i = 0;i < s.size();++i){ result[i][i] = true; }</span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> start = <span style="color: #800080;">0</span>;start < s.size() - <span style="color: #800080;">1</span>;++<span style="color: #000000;">start){ result[start][start </span>+ <span style="color: #800080;">1</span>] = s[start] == s[start + <span style="color: #800080;">1</span><span style="color: #000000;">]; } </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> len = <span style="color: #800080;">2</span>; len < s.size();++<span style="color: #000000;">len){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> start = <span style="color: #800080;">0</span>;start < s.size() - len;++<span style="color: #000000;">start){ result[start][start </span>+ len] =<span style="color: #000000;"> (result[start </span>+ <span style="color: #800080;">1</span>][start + len - <span style="color: #800080;">1</span>] && s[start] == s[start +<span style="color: #000000;"> len]); } } </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> result; } </span><span style="color: #0000ff;">int</span> minCut(<span style="color: #0000ff;">string</span><span style="color: #000000;"> s) { </span><span style="color: #0000ff;">if</span>(s.size() == <span style="color: #800080;">0</span><span style="color: #000000;">){ </span><span style="color: #0000ff;">return</span> -<span style="color: #800080;">1</span><span style="color: #000000;">; } vector</span><vector<<span style="color: #0000ff;">bool</span>>> result =<span style="color: #000000;"> isPalindrome(s); </span><span style="color: #0000ff;">int</span> n =<span style="color: #000000;"> s.size(); </span><span style="color: #008000;">//</span><span style="color: #008000;">state</span> vector<<span style="color: #0000ff;">int</span>> f(n + <span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>);<span style="color: #008000;">//</span><span style="color: #008000;">最少需要多少刀 </span><span style="color: #008000;">//</span><span style="color: #008000;">intialization </span> <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i <= n;++<span style="color: #000000;">i){ f[i] </span>= i - <span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #008000;">//</span><span style="color: #008000;">function </span> <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>;i <= n;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">0</span>;j < i;++<span style="color: #000000;">j){ </span><span style="color: #0000ff;">if</span>(result[j][i - <span style="color: #800080;">1</span><span style="color: #000000;">]){ f[i] </span>= min(f[j] + <span style="color: #800080;">1</span><span style="color: #000000;">,f[i]); } } } </span><span style="color: #008000;">//</span><span style="color: #008000;">answer</span> <span style="color: #0000ff;">return</span><span style="color: #000000;"> f[n]; }};
二刷版本：注意主程序需要考虑i == j。len从1开始，也可以考虑dp[n] ，不一定要dp[n + 1];
class Solution { public:</span><span style="color: #0000ff;">void</span> judge(vector<vector<<span style="color: #0000ff;">bool</span>>> &res,<span style="color: #0000ff;">string</span><span style="color: #000000;"> s){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < res.size();++<span style="color: #000000;">i){ res[i][i] </span>= <span style="color: #0000ff;">true</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < res.size();++<span style="color: #000000;">i){ res[i][i </span>+ <span style="color: #800080;">1</span>] = (s[i] == s[i + <span style="color: #800080;">1</span><span style="color: #000000;">]); } </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> len = <span style="color: #800080;">1</span>;len < res.size();++<span style="color: #000000;">len){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < res.size() - len - <span style="color: #800080;">1</span>;++<span style="color: #000000;">i){ res[i][i </span>+ len + <span style="color: #800080;">1</span>]= res[i + <span style="color: #800080;">1</span>][i + len] && (s[i] == s[i + len + <span style="color: #800080;">1</span><span style="color: #000000;">]); } } } </span><span style="color: #0000ff;">int</span> minCut(<span style="color: #0000ff;">string</span><span style="color: #000000;"> s) { </span><span style="color: #0000ff;">if</span><span style="color: #000000;">(s.empty()){ </span><span style="color: #0000ff;">return</span> -<span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">int</span> n =<span style="color: #000000;"> s.size(); vector</span><vector<<span style="color: #0000ff;">bool</span>>> res(n,vector<<span style="color: #0000ff;">bool</span>> (n,<span style="color: #0000ff;">false</span><span style="color: #000000;">)); vector</span><<span style="color: #0000ff;">int</span>> dp(n,<span style="color: #800080;">0</span><span style="color: #000000;">); judge(res,s); </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < n;++<span style="color: #000000;">i){ dp[i] </span>=<span style="color: #000000;"> i; } </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>;i < n;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">0</span>;j <= i;++j){<span style="color: #008000;">//</span><span style="color: #008000;">这里一定要i==j结束</span> <span style="color: #0000ff;">if</span><span style="color: #000000;">(res[j][i]){ </span><span style="color: #0000ff;">if</span>(j == <span style="color: #800080;">0</span><span style="color: #000000;">){ dp[i] </span>= <span style="color: #800080;">0</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ dp[i] </span>= min(dp[i],dp[j - <span style="color: #800080;">1</span>] + <span style="color: #800080;">1</span><span style="color: #000000;">); } } } } </span><span style="color: #0000ff;">return</span> dp[n - <span style="color: #800080;">1</span><span style="color: #000000;">]; }};
4.6 139. Word Break
https://leetcode.com/problems/word-break/description/
这道拆分词句问题是看给定的词句能分被拆分成字典里面的内容
思路：就是按照动态规划四步走战略，注意判断前提：首先是yes/no问题，然后是序列不是集合，所以是序列型动态规划。
1）预处理：使用unordered_set，将字典存储，这样以后查找才快；
2）state：vector<bool> f(n + 1,false);//前i个字符是否能分割为dictionary里面的单词；
3）intialization： f[0] = true;空字符肯定是存在的。
4）//function：前j个是字典中的并且j和i中间的单词也是字典中的，那么前i个就是TRUE,
if(f[j] == true && setWordDict.find(subString) != setWordDict.end()){ f[i] = true; }
5)answer:f[n]。
class Solution { public: set<string> WordDict(vector<string>& wordDict){ set<string> result; for(string str : wordDict){ result.insert(str); } return result; } bool wordBreak(string s, vector<string>& wordDict) { if(s.size() == 0){ return true; } if(wordDict.size() == 0){ return false; } //preparation set<string> setWordDict = WordDict(wordDict); //state int n = s.size(); vector<bool> f(n + 1,false);//前i个字符是否能分割为dictionary里面的单词 //intialization f[0] = true; //function for(int i = 1;i <= n;++i){ for(int j = 0;j < i;++j){ string subString = s.substr(j,i - j);//（i - 1） -j + 1 if(f[j] == true && setWordDict.find(subString) != setWordDict.end()){ f[i] = true; } } } //answer return f[n]; } };
二刷错误点
1）goals,,字典是go,goal,goals
所以不能一找到第一个go就break。
2）
int ix = 0; for(ix = 0;ix < n;++ix){ if(wordSet.find(s.substr(0,ix + 1)) != wordSet.end()){ dp[ix] = true; //break; } } // if(ix == n){ // return dp[ix - 1]; // }开始这里没注释，直接每次退出循环ix都等于n，总是出错，因为是原来break掉，才有这句
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { if(s.size() == 0){ return false; } if(wordDict.size() == 0){ return 0; } int n = s.size(); vector<bool> dp(n,false); //hashset unordered_set<string> wordSet; for(int i = 0;i < wordDict.size();++i){ wordSet.insert(wordDict[i]); } //find first true int ix = 0; for(ix = 0;ix < n;++ix){ if(wordSet.find(s.substr(0,ix + 1)) != wordSet.end()){ dp[ix] = true; //break; } } // if(ix == n){ // return dp[ix - 1]; // }开始这里没注释，直接每次退出循环ix都等于n，总是出错，因为是原来break掉，才有这句 //funciton for(int i = 0;i < n;++i){ for(int j = 1;j <= i;++j){ if((dp[j - 1] == true) && (wordSet.find(s.substr(j,i - j + 1)) != wordSet.end())){ dp[i] = true; } } }</span><span style="color: #0000ff;">return</span> dp[n - <span style="color: #800080;">1</span><span style="color: #000000;">]; }};
那道题只让我们判断给定的字符串能否被拆分成字典中的词，而这道题加大了难度，让我们求出所有可以拆分成的情况，
5、双序列型动态规划。
一定要注意：不管是双序列还是单序列动态规划，都必须注意求前n个这种情况。比如：seq和f[i],f数组中f[i]，对应到seq中的计算必须是seq[i - 1]。
5.1 Longest Common Subsequence
最长公共子序列
http://www.lintcode.com/en/problem/longest-common-subsequence/
思路：1）f[i][j]代表a前i个字符和b前j个字符的相等的长度。
这题最容易错的地方就是：seq和f[i],f数组中f[i]，对应到seq中的计算必须是seq[i - 1]，毕竟在状态定义中，f数组指的是前i个字符。
2)intialization:初始化为0；
3）function：就是递推方程；
4)answer:f[n][m]。
class Solution { public: /** * @param A, B: Two strings. * @return: The length of longest common subsequence of A and B. */ int longestCommonSubsequence(string A, string B) { // write your code here if(A.size() == 0 || B.size() == 0){ return 0; } int n = A.size(); int m = B.size(); //state vector<vector<int>> f(n + 1,vector<int> (m + 1,0)); //intialization</span><span style="color: #008000;">//</span><span style="color: #008000;">function</span> <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>;i <= n;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">1</span>;j <= m;++<span style="color: #000000;">j){ </span><span style="color: #0000ff;">if</span>(A[i - <span style="color: #800080;">1</span>] == B[j - <span style="color: #800080;">1</span><span style="color: #000000;">]){ f[i][j ] </span>= f[i - <span style="color: #800080;">1</span>][j - <span style="color: #800080;">1</span>] + <span style="color: #800080;">1</span><span style="color: #000000;">; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ f[i][j] </span>= max(f[i][j - <span style="color: #800080;">1</span>],f[i - <span style="color: #800080;">1</span><span style="color: #000000;">][j]); } } } </span><span style="color: #008000;">//</span><span style="color: #008000;">answer</span> <span style="color: #0000ff;">return</span><span style="color: #000000;"> f[n][m]; }};
5.2 72. Edit Distance
https://leetcode.com/problems/edit-distance/description/
将字符串1变为字符串2，最小的编辑距离。
这里注意一个错误信息：min函数里面比较的只能是两个数，如果比较三个数就会出错“required from here ”。
思路：1）state：f[i][j]a中的前i 个字符经过多少次编辑变为b中的前j个字符。
2）function：f[i][j] = MIN( f[i-1][j]+1插入, f[i][j-1]+1删除, f[i-1][j-1]不变 ) // a[i] == b[j]
= MIN( f[i-1][j]+1插入, f[i][j-1]+1删除, f[i-1][j-1]+1替换 ) // a[i] != b[j]
（帮助记忆：假设i等于j，i-1就是需要增加一个才能等于j,j - 1就需要i删除一个才能使得两者相等）
3）intialize：f[i][0] = i, f[0][j] = j ；
4）answer: f[a.length()][b.length()]
class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(),m = word2.size(); if(n == 0 && m == 0){ return 0; } //state vector<vector<int>> f(n + 1,vector<int> (m + 1,0)); //intialization for(int i = 0;i <= n;++i){ f[i][0] = i; } for(int j = 0;j <= m;++j){ f[0][j] = j; } //function for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ if(word1[i - 1] == word2[j - 1]){ f[i][j] = min(f[i - 1][j - 1],min(f[i][j - 1] + 1,f[i - 1][j] + 1)); } else{f[i][j] </span>= min(f[i - <span style="color: #800080;">1</span>][j - <span style="color: #800080;">1</span>] + <span style="color: #800080;">1</span>,min(f[i][j - <span style="color: #800080;">1</span>] + <span style="color: #800080;">1</span>,f[i - <span style="color: #800080;">1</span>][j] + <span style="color: #800080;">1</span><span style="color: #000000;">)); } } } </span><span style="color: #008000;">//</span><span style="color: #008000;">answer</span> <span style="color: #0000ff;">return</span><span style="color: #000000;"> f[n][m]; }};
5.3 115. Distinct Subsequences
https://leetcode.com/problems/distinct-subsequences/description/
思路：题目意思是source字符串中找出和target字符串相等的子串有多少个。记住那两个for循环，一个是i <=n,j<= m，只要是双序列动态规划都是这样。
初始化的时候，要注意初始化第一个f[0[0],初始化第一个列和第一行会重复第1个，所以要注意这里。初始化技巧先全部初始化为0，后面就看哪些情况不是0的就特殊处理就好了。
//intialize for(int i = 0;i <= n;++i){ f[i][0] = 1; cout << f[i][0]; } for(int j = 1;j <= m;++j){//初始化第一个f[0][0]出现冲突，导致出错 f[0][j] = 0; }
state: f[i][j] 表示 S的前i个字符中选取T的前j个字符，有多少种方案
function:第j个字符是不能去掉的，都是分为相等和不相等这两种情况进行处理，
如果i和j相等，就看前i-1个字符和前j个字符的情况以及前i-1和j-1个字符判断，
不相等的话就看前i-1个字符和前j个字符的情况。
f[i][j] = f[i - 1][j] + f[i - 1][j - 1] (S[i-1] == T[j-1])
= f[i - 1][j] (S[i-1] != T[j-1])
initialize: f[i][0] = 1, f[0][j] = 0 (j > 0)
answer: f[n][m] (n = sizeof(S), m = sizeof(T))
class Solution { public: int numDistinct(string s, string t) { int n = s.size(); int m = t.size(); if(n == 0 && m == 0){ return 1; } //state vector<vector<int>> f(n + 1,vector<int> (m + 1,0)); //intialize for(int i = 0;i <= n;++i){ f[i][0] = 1; cout << f[i][0]; } for(int j = 1;j <= m;++j){//初始化第一个f[0][0]出现冲突，导致出错 f[0][j] = 0; } //function<span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>;i <= n;++<span style="color: #000000;">i){ </span><span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> j = <span style="color: #800080;">1</span>;j <= m;++<span style="color: #000000;">j){ </span><span style="color: #0000ff;">if</span>(s[i - <span style="color: #800080;">1</span>] == t[j - <span style="color: #800080;">1</span><span style="color: #000000;">]){ f[i][j] </span>= f[i - <span style="color: #800080;">1</span>][j] + f[i - <span style="color: #800080;">1</span>][j - <span style="color: #800080;">1</span><span style="color: #000000;">]; } </span><span style="color: #0000ff;">else</span><span style="color: #000000;">{ f[i][j] </span>= f[i - <span style="color: #800080;">1</span><span style="color: #000000;">][j]; } } } </span><span style="color: #008000;">//</span><span style="color: #008000;">answer</span> <span style="color: #0000ff;">return</span><span style="color: #000000;"> f[n][m]; }};
5.4 97. Interleaving String
s3是否是由s1和s2交错形成的字符串。
思路：先填满一个dp数组，然后想第一行第一列，然后找规律得递推关系。参考交织相错的字符串。只要是遇到字符串的子序列或是匹配问题直接就上动态规划Dynamic Programming，其他的都不要考虑。
技巧：初始化的时候先单独初始化第一个，然后再循环初始化第一行和第一列。
state: f[i][j]表示s1的前i个字符和s2的前j个字符能否交替组成s3的前i+j个字符
前i个和前j个组成前i + j个，对应的下标是i + j - 1
function: f[i][j] = (f[i-1][j] && (s1[i-1]==s3[i+j-1]) || f[i][j-1] && (s2[j-1]==s3[i+j-1])----注意f数组是前i个，对应s数组下标是i-1.
initialize: f[i][0] = s1[0..i-1] = s3[0..i-1]
f[0][j] = s2[0..j-1] = s3[0..j-1]
answer: f[n][m] n = sizeof(s1), m = sizeof(s2)
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if(s1.size() + s2.size() != s3.size()){ return false; } int n = s1.size(),m = s2.size(); //state vector<vector<bool>> dp(n + 1,vector<bool> (m + 1,false)); //intialize dp[0][0] = true; for(int i = 1;i <= n;++i){ if(s1[i - 1] == s3[i - 1] && dp[i - 1][0] == true){ dp[i][0] = true; } } for(int j = 1;j <= m;++j){ if(s2[j - 1] == s3[j - 1] && dp[0][j - 1] == true){ dp[0][j] = true; } } //function for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ if(s1[i - 1] == s3[i - 1 + j] && dp[i - 1][j] || s2[j - 1] == s3[i - 1 + j] && dp[i][j - 1]){ dp[i][j] = true; } } } return dp[n][m]; } };