动态规划介绍
动态规划（Dynamic Programming）简称dp，它是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
特点
动态规划具备了以下三个特点：
把原来的问题分解成了几个相似的子问题。
所有的子问题都只需要解决一次。
储存子问题的解。
解题思路
动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)，动态规划问题一般从以下四个角度考虑：
明确问题
状态定义（根据问题从中抽象出来状态）
状态转移方程定义
状态初始化
返回结果
适用场景：最大值/最小值, 可不可行, 是不是，方案个数。
一. 矩阵系列
1、查找两个字符串a,b中的最长公共子串
题目连接
题目描述：
查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。本题含有多组输入数据！
输入描述：
输入两个字符串。
输出描述：
返回重复出现的字符。
示例：
输入
abcdefghijklmnop
abcsafjklmnopqrstuvw
输出
jklmnop
解题思路：
先创建一个二维数组保存公共子串长度，以较小串的长度+1为行数，较大串的长度+1为列数，初始值全为0。
较大串的第一个字符开始在较小串中全部查找一遍，如果有该字符则更新数组对应位置的值，直到较大字符串遍历完。
更新方式为count[i][j] = count[i-1][j-i]+1，在此过程中不断更新最大子串的长度max及起始位置start。
完整代码：
#include <string> #include <vector> #include <iostream> using namespace std; string Find(const string& s1, const string& s2) { int start = 0; int maxLength = 0; int len1 = s1.size(); int len2 = s2.size(); vector<vector<int>> count(len1 + 1, vector<int>(len2 + 1)); for(int i = 1; i <= len1; ++i) { for(int j = 1; j <= len2; ++j) { // 更新当前位置 if(s1[i-1] == s2[j-1]) { count[i][j] = count[i-1][j-1] + 1; } if(count[i][j] > maxLength) { maxLength = count[i][j]; start = i-maxLength; } } } return s1.substr(start, maxLength); } int main() { string s1; string s2; // 设置s1为较小长度的串 while (cin >> s1 >> s2) { if (s2.size() < s1.size()) { s1.swap(s2); } cout << Find(s1, s2) << endl; } return 0; }
性能分析：
时间复杂度：O(len1 * len2)。len1、len2对对应最小、最大串的长度，动态规划需要遍历整个数组来完善数据，最终得到结果。
空间复杂度：O(len1 * len2)。数组空间开销。
2、计算字符串距离
题目连接
题目描述：
输入描述：
每组用例一共2行，为输入的两个字符串
输出描述：
每组用例输出一行，代表字符串的距离
示例：
输入：
abcdefg
abcdef
abcde
abcdf
abcde
bcdef
输出：
1
1
2
解题思路：
参考这张图，黑色数字的行和列分别表示，其中一个字符串相对于另一个空字符串的编辑距离，红色部分表示两个字符串均非空的情况。
if （i ≥ 1 且 j ≥ 1） ，对比新加的字符
新加的字符如果相同，不需要任何变换则当前位置的距离等于前一位置的距离：distance(i, j) = distance(i-1, i+1)
如果不相同，在之前的编辑距离计算好的基础上+1取最小值。
distance(i, j) == min{ distance(i-1, j) + 1, distance(i, j-1) + 1, edit(i-1, j-1) + 1 }
完整代码：
#include <vector> #include <iostream> using namespace std; size_t StringDistance(const string& s1, const string& s2) { // 1、创建出一个len1+1*len2+1大小的数组 size_t len1 = s1.size(); size_t len2 = s2.size(); vector<vector<size_t>> distance(len1+1, vector<size_t>(len2+1)); // 2、初始化最开始数据 for(size_t i = 1; i <= len1; ++i) { distance[i][0] = i; } for(size_t j = 1; j <= len2; ++j) { distance[0][j] = j; } // 3、动态规划处理每一种情况，直到最后位置 for(size_t i = 1; i <= len1; ++i) { for(size_t j = 1; j <= len2; ++j) { if(s1[i-1] == s2[j-1]) { distance[i][j] = distance[i-1][j-1]; } else { distance[i][j] = min(min(distance[i-1][j]+1, distance[i][j-1]+1), distance[i-1][j-1]+1); } } } return distance[len1][len2]; } int main() { string s1; string s2; while(cin>>s1>>s2) { cout<<StringDistance(s1, s2)<<endl; } return 0; }
性能分析：
时间复杂度：O(len1 * len2)。
空间复杂度：O(len1 * len2)。
3、年终奖
题目连接
题目描述：
小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
解题思路：
题目规定只能往下走或者往右走，那么当前位置肯定是从上面或者左边过来的，即当前能拿取礼物的最大价值就是max(上面位置的最大礼物价值，左面位置的最大礼物价值)+当前位置礼物价值。
先处理最上一排和最左一列的数据。
根据状态方程处理中间位置数据：board[i][j] += max（board[i-1][j], board[i][j-1]）;
完整代码：
class Bonus { public: int getMost(vector<vector<int> > board) { // 1、先处理最上一排和最左一列位置的数据 for(int i = 1; i < 6; ++i) { board[0][i] += board[0][i-1]; board[i][0] += board[i-1][0]; } // 2、处理中间位置的数据 for(int i = 1; i < 6; ++i) { for(int j = 1; j < 6; ++j) { board[i][j] += max(board[i-1][j], board[i][j-1]); } } // 3、最终右下角的值就是最大礼物价值 return board[5][5]; } };
性能分析：
时间复杂度：O(n)。需要处理每一个位置的元素。
空间复杂度：O(1)。
4、编辑距离
题目连接
解题思路：
问题：求word1到word2的编辑距离。
状态定义：dp[i][j] — word1的[0, i-1]区间字符到word2的[0, j-1]区间字符的编辑距离。
状态转移方程：dp[i][j] = 下面三种情况取最小
增加一个字符：dp[i-1][j] + 1
删除一个字符：dp[i][j-1] + 1
替换一个字符：
如果word1[i-1] == word2[j-1]的话，dp[i-1][j-1]
否则，dp[i-1][j-1] + 1
状态初始化：
dp[i][0] = i，表示逐个删除字符使word1变成word2（空串）
dp[0][j] = j，表示逐个插入字符使word1（空串）变成word2
返回结果：dp[word1.size()][word2.size()]
完整代码：
class Solution { public: int minDistance(string word1, string word2) { int row = word1.size(); int col = word2.size(); vector<vector<int>> distances(row+1, vector<int>(col+1)); // 1、状态初始化 for(int i = 0; i <= row; ++i) { distances[i][0] = i; } for(int j = 0; j <= col; ++j) { distances[0][j] = j; } // 2、状态转移 for(int i = 1; i <= row; ++i) { for(int j = 1; j <= col; ++j) { distances[i][j] = min(distances[i-1][j], distances[i][j-1]) + 1; if(word1[i-1] == word2[j-1]) { distances[i][j] = min(distances[i][j], distances[i-1][j-1]); } else { distances[i][j] = min(distances[i][j], distances[i-1][j-1] + 1); } } } // 3、返回结果 return distances[row][col]; } };
性能分析：
时间复杂度：O(mn)。
空间复杂度：O(mn)。
二. 最大子序和系列
从动态规划角度讲，最大子数组和是以一类较简单的 DP 问题，但它的状态设计比较经典，同时也是很多问题的基础组件。
1、最大子序和
题目连接
题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：
题目已经保证了至少有一个元素，我们定义两个变量，一开始它们的值都是nums[0]。
cur：记录当前下标i位置的最大连续子数组和（注意要加上nums[i]）。
ret：记录最大连续子数组和。
从下标为1的位置开始遍历根据状态转移方程更新cur和ret。
状态转移方程：cur = num[i] + max(cur, 0);
完整代码：
class Solution { public: int maxSubArray(vector<int>& nums) { int ret = nums[0]; int cur = nums[0]; for(int i = 1; i < nums.size(); ++i) { cur = nums[i] + max(cur, 0); if(cur > ret) { ret = cur; } } return ret; } };
性能分析：
时间复杂度：O(n)。
空间复杂度：O(1)
2、乘积最大子数组
题目连接
题目描述：
给你一个整数数组nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
解题思路：
参考最大子序和的思路，当前位置的乘积最大子数组 dp[i] = max(dp[i - 1] * nums[i], nums[i])，但是对于乘法而言存在负负得正的情况，所以不能简单的就这样套用。
考虑当前位置的元素cur：
如果cur是个正数，我们希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。
如果cur是个负数，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。
对于上面的两种情况我们维护两个状态方程，以保证得到最终正确的结果：
完整代码：
class Solution { public: int maxProduct(vector<int>& nums) { int ret = nums[0]; int curMax = nums[0]; int curMin = nums[0]; for(int i = 1; i < nums.size(); ++i) { int mx = curMax; int mn = curMin; curMax = max(nums[i], max(nums[i] * mx, nums[i] * mn)); curMin = min(nums[i], min(nums[i] * mx, nums[i] * mn)); ret = max(curMax, ret); } return ret; } };
性能分析：
时间复杂度：O(n)。只需遍历一次数组即可。
空间复杂度：O(1)。
3、环形子数组的最大和
题目连接
题目描述：
解题思路：
该题目是最大连续子序和的变种。分两种情况分析：
最大连续子序和在中间，和平时一样的解法。
最大连续子序和跨越头尾，此时从两边出发往中间靠拢的和是最大，那就说明中间的和是最小，我们只需找中间和最小的，用数组的总和减去这个最小的就是我们要的结果。
完整代码：
class Solution { public: int maxSubarraySumCircular(vector<int>& nums) { int sum = nums[0]; int curMax = nums[0]; int curMin = nums[0]; int allMax = nums[0]; int allMin = nums[0]; // 1、正常计算该数组的最大子数组和 for(size_t i = 1; i < nums.size(); ++i) { sum += nums[i]; curMax = max(nums[i], curMax + nums[i]); allMax = max(allMax, curMax); } // 2、正常计算该数组的最小子数组和 // 循环终止条件是“i < nums.size() - 1”的原因： // 如果最大连续子数组和跨越了头尾，根据ret = sum - allMin // allMin一定不会包括最后一个因素，这个元素一定是在ret中的，当然不减一也可以通过。 for(size_t i = 1; i < nums.size() - 1; ++i) { curMin = min(nums[i], curMin + nums[i]); allMin = min(allMin, curMin); } // 3、看是中间的连续子数组大还是贯穿头尾的连续子数组大 return max(allMax, sum == allMin? sum : sum - allMin); } };
性能分析：
时间复杂度：O(n)。一共遍历两次数组。
空间复杂度：O(1)。
三. 最长递增子序列（LIS）系列
最长递增子序列（Longest increasing subsequence, LIS）是个经典的动态规划问题，很多单串的题目的状态设计都是启发自这道题来设计的。
1、最长递增子序列
题目描述
题目描述：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解题思路：
创建整型数组count用来记录到当前下标位置的最长递增子序列的长度，一开始都只算自己，所以都初始化为1。
遍历[0, i-1]区间的nums元素，找到小于nums[i]的元素。
通过状态转移方程：count[ i ] = max(count[ i ], counnt[ j ]+1);来更新count[ i ]。
最后取counnt中最大值就是最终结果。
完整代码：
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> count(nums.size(), 1); for(size_t i = 1; i < nums.size(); ++i) { for(int j = 0; j < i; ++j) { if(nums[j] < nums[i]) { count[i] = max(count[i], count[j]+1); } } } return *max_element(count.begin(), count.end()); } };
性能分析：
时间复杂度：O(n^2)。两层for循环。
空间复杂度：O(n)。处理一个count[ i ]，需要用到前面[0, i-1]区间的所有数据，所以要创建一个长度为n的count数组。
2、俄罗斯套娃信封问题
题目连接
题目描述：
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
解题思路：
对envelopes的每一个元素进行排序：对宽度升序，并且在宽度相同时对高度降序，这样做的目的有两个：
保证迭代排序后的envelopes时，宽度是非递减的（注意：相邻的两个envelope可能宽度相同）
在相邻两个envelope宽度相同的情况时，两者的高度是非递增的，比如(3, 5), (3, 3), 不会出现“相同高度，后者套前者”的情况。
随后我们就可以忽略宽度，求出以高度为基准的最长严格递增子序列，其长度即为答案。
完整代码：
// sort会把传入的每一个元素解引用之后再传入MyCompare中作比较 // 所以MyCompare的参数类型为vector<int> // 如果返回true，则让e1排到e2之前 // 如果返回false，则让e1排到e2之后 // 如果要把MyCompare定义到类内部的话需要加static修饰，这样sort中调用时不会因为没有this指针而报错 // 也可以把MyCompare定义到类外 int MyCompare(const vector<int>& e1, const vector<int>& e2) { if(e1[0] < e2[0]) { return 1; } else if(e1[0]==e2[0] && e1[1]>e2[1]) { return 1; } return 0; } class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { sort(envelopes.begin(), envelopes.end(), MyCompare); vector<int> count(envelopes.size(), 1); for(int i = 1; i < envelopes.size(); ++i) { for(int j = 0; j < i; ++j) { if(envelopes[j][1] < envelopes[i][1]) { count[i] = max(count[i], count[j]+1); } } } return *max_element(count.begin(), count.end()); } };
性能分析：
时间复杂度：动态规划需要的时间复杂度为 O(n^2)。
空间复杂度：数组count的开销。
3、最长递增子序列的个数
题目连接
题目描述：
给定一个未排序的整数数组，找到最长递增子序列的个数。
解题思路：
这题是最长递增子序列的进阶版本，最原题的基础上再维护一个cnt数组用来统计当前位置的最长递增序列的个数。
该题的用到的两个状态转移方程说明：
dp[i]：代表第个i位置上的最长递增子序列的长度。
cnt[i]：代表第i个位置上的最长递增子序列的个数。
当 j < i 且 nums[j] < nums[i] 时：
如果dp[j] + 1 > dp[i]，更新i位置的最长递增子序列长度dp[i] = dp[j] + 1，并重置cnt[i] = cnt[j]。
否则如果dp[j] + 1 == dp[i]的话，更新cnt[i] += cnt[j]。
完整代码：
class Solution { public: int findNumberOfLIS(vector<int>& nums) { int ret = 1; int maxLen = 1; vector<int> dp(nums.size(), 1); vector<int> cnt(nums.size(), 1); for(size_t i = 1; i < nums.size(); ++i) { for(size_t j = 0; j < i; ++j) { if(nums[j] < nums[i]) { if(dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; cnt[i] = cnt[j];// 重置计数 } else if(dp[j] + 1 == dp[i]) { cnt[i] += cnt[j];// 更新计数 } } } if(dp[i] > maxLen) { maxLen = dp[i]; ret = cnt[i]; } else if(dp[i] == maxLen) { ret += cnt[i]; } } return ret; } };
性能分析：
时间复杂度：O(n^2)。处理当前位置的状态转移方程时需要参考前面i-1个已处理好了的数据。
空间复杂度：O(n)。
四. Fibonacci系列
1、斐波那契数列
题目连接
题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
解题思路
状态定义：F(n)，第n个斐波那契数的值
状态转移方程：F(n) = F(n-1) + F(n-2)
状态初始化：F(0) = 0，F(1) = 1
返回结果：F(n)
完整代码
class Solution { public: int Fibonacci(int n) { if(n == 0) return 0; if(n == 1) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } };
时间复杂度：O(2^n)，递归次数是公比为2的等比数列之和。
空间复杂度：O(2^n)。
优化版本一
上面的递归的方法时间复杂度为O(2^n)，随着n的增大呈现指数增长，效率低下，这是因为在递归过程中有大量的重复计算，当输入比较大时，可能导致栈溢出使用。
下面循环迭代的方法来减少递归不可避免的重复计算：
class Solution { public: int Fibonacci(int n) { if(n == 0) return 0; if(n == 1) return 1; // 申请一个数组，保存子问题的解 vector<int> Fib(n+1); Fib[0] = 0; Fib[1] = 1; for(int i = 2; i <= n; ++i) { Fib[i] = Fib[i-1] + Fib[i-2]; } return Fib[n]; } };
时间复杂度：O(n)。
空间复杂度：O(n)。
最终优化版本
上述解法的空间复杂度为O(n)，其实Fib(n)只与它相邻的前两项有关，所以没有必要保存所有子问题的解，只需要保存两个子问题的解就可以。
下面方法的空间复杂度将优化为O(1)：
class Solution { public: int Fibonacci(int n) { if(n == 0) return 0; if(n == 1 || n == 2) return 1; int fn1 = 1; int fn2 = 1; int fn = 0; for(int i = 3; i <= n; ++i) { fn = fn1 + fn2; fn2 = fn1; fn1 = fn; } return fn; } };
时间复杂度：O(n)。
空间复杂度：O(1)。
五. 路径系列
1、三角矩阵最短路径和
题目连接
题目描述：
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
方法一：自顶向下求解
问题： 找出自顶向下的最小路径和。
状态定义：dp[i][j] — 自顶到[i][j]位置的最小路径和。
状态转移方程：
当0<j<i时：dp[i][j] = min(dp[i-1][i] + dp[i-1][j-1]) + array[i][j]
当j==0时：dp[i][j] = dp[i-1][j] + array[i][j]
当i==j时：dp[i][j] = dp[i-1][j-1] + array[i][j]
状态初始化：dp[0][0] = array[0][0]
返回结果：min(dp[ROW-1][j])
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { // 计算出三角矩阵的最大行数 size_t row = triangle.size(); // 1、动态规划算出所有位置的最小路径和 for (size_t i = 1; i < row; ++i) { for (size_t j = 0; j <= i; ++j)// 不要用j <= triangle[i].size() { if (j == 0) triangle[i][j] += triangle[i - 1][j]; else if (j == i) triangle[i][j] += triangle[i - 1][j - 1]; else triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1]); } } // 2、拿到自顶向下的最小路径和 int minSum = triangle[row - 1][0]; for (size_t j = 1; j < row; ++j)// 不要用j <= triangle[row-1].size() { minSum = min(minSum, triangle[row - 1][j]); } return minSum; } };
方法二：自底向上求解
从倒数第二行开始往上求解，不用考虑边界元素：
状态定义：dp[i][j] — 自底到[i][j]位置的最小路径和。
状态转移方程：dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + array[i][j];
态初始化：dp[ROW.size()-1][j] = array[ROW.size()-1][j];
返回结果：dp[0][0]
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { size_t row = triangle.size(); for(int i = row-2; i >= 0; --i) { for(int j = 0; j <= i; ++j) { triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]); } } return triangle[0][0]; } };
性能分析：
两种方法效率上没有差别，不过方法二的代码写出来更加简洁。
时间复杂度：O(n)。其中n代表三角矩阵中元素的个数。
空间复杂度：O(n)。一般不能修改原数组的数据，所以拷贝原二维矩阵需要n的空间。
2、方形矩阵路径数目
题目连接
解题思路：
问题：求起点到终点的路径的数目。
状态定义：dp[i][j] — 从起点到(i, j)位置的路径的数目。
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
状态初始化：dp[0][j] = dp[i][0] = 1
返回结果：dp[m-1][n-1]
完整代码：
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); // 1、状态初始化 for(size_t i = 0; i < m; ++i) { dp[i][0] = 1; } for(size_t j = 1; j < n; ++j) { dp[0][j] = 1; } // 2、动态规划处理中间的所有dp[i][j] for(size_t i = 1; i < m; ++i) { for(size_t j = 1; j < n; ++j) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } // 3、返回最终结果 return dp[m-1][n-1]; } };
性能分析：
时间复杂度：O(mn)。
空间复杂度：O(mn)。
3、方形矩阵最短路径和
题目连接
解题思路：
问题：左上角到右下角的最短路径和。
状态定义：dp[i][j] — (0, 0)到(i, j)的最短路径和。
状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1])+array[i][j]
状态初始化：dp[0][0] = array[0][0]， dp[0][j] = dp[0][j-1]+array[0][j]， dp[i][0] = dp[i-1][0]+array[i][0]
返回结果：dp[row-1][col-1]
完整代码：
class Solution { public: int minPathSum(vector<vector<int> >& grid) { size_t row = grid.size(); size_t col = grid[0].size(); // 1、状态初始化 for(size_t j = 1; j < col; ++j) { grid[0][j] = grid[0][j-1] + grid[0][j]; } for(size_t i = 1; i < row; ++i) { grid[i][0] = grid[i-1][0] + grid[i][0]; } // 2、中间范围的(i, j)数据计算 for(size_t i = 1; i < row; ++i) { for(size_t j = 1; j < col; ++j) { grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]; } } // 3、返回终点结果 return grid[row-1][col-1]; } };
性能分析：
时间复杂度：O(mn)。
空间复杂度：O(mn)。
六. 背包问题
1、01背包
题目连接
解题思路：
问题：最多能装入背包的总价值是多大。
状态定义：dp[i][j] — (dp中的的i从1开始，对应到数组就是下标为i-1的那个物品)，前i个物品（包括第i个）放到容量为j的背包中，最大价值是多少。
状态转移方程：
w[i] <= j时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
w[i] > j时，dp[i][j] = dp[i-1][j];
状态初始化：dp[0][j] = dp[i][0] = 0
返回结果：dp[i][j]
方法一：二维数组：
class Solution { public: int backPackII(int m, vector<int> &a, vector<int> &v) { // 1、状态初始化 int n = a.size(); vector<vector<int>> dp(n+1, vector<int>(m+1)); // 2、利用状态转移方程计算出所有位置的dp[i][j]的值 for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(a[i-1] <= j) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1]] + v[i-1]); } else { dp[i][j] = dp[i-1][j]; } } } // 3、返回结果 return dp[n][m]; } };
时间复杂度：O(nm)
空间复杂度：O(nm)。
方法二：一维数组：
class Solution { public: int backPackII(int m, vector<int>& a, vector<int>& v) { // 1、状态初始化 int n = a.size(); vector<int> dp(m + 1); // 2、利用状态转移方程计算出所有位置的dp[i][j]的值 for (int i = 1; i <= n; ++i) { for (int j = m; j >= 1; --j) { if (a[i - 1] <= j) { dp[j] = max(dp[j], dp[j - a[i - 1]] + v[i - 1]); } } } // 3、返回结果 return dp[m]; } };
时间复杂度：O(nm)
空间复杂度：O(m)。
七. 待分类
1、拆分词句
题目连接
题目描述
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
例如:
给定s=“nowcode”；
dict=[“now”, “code”]
返回true，因为"nowcode"可以被分割成"now code"
解题思路
问题：判断字符串是否能被分割成一个单词序列
状态定义：dp[i] — 前i个字符能否被分割
状态转移方程：dp[i] = (j<i && dp[j] && [j+1, i]存在于dict中)
状态初始化：dp[0] = true
返回结果：dp[s.size()]
完整代码
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { vector<bool> canBreak(s.size()+1, false); canBreak[0] = true; for(size_t i = 1; i <= s.size(); ++i) { for(size_t j = 0; j < i; ++j) { if(canBreak[j] && (dict.find(s.substr(j, i-j)) != dict.end())) { canBreak[i] = true; break; } } } return canBreak[s.size()]; } };
性能分析
时间复杂度：O(n^2)。
空间复杂度：O(n^2)。
2、分割回文串
题目连接
解题思路：
问题：把字符串s分割成回文子串的最小分割次数。
状态定义：dp[i] — i从1开始，把前面的i个字符分割成回文子串的最小分割次数。
状态转移方程：
[0, i-1]直接是回文串，dp[i] = 0
否则：(j < i && [j+1, i-1]是回文串) —> 更新dp[i] = min(dp[i], dp[j]+1)
状态初始化：dp[i] = i-1
返回结果：dp[s.size()]
完整代码：
class Solution { public: int minCut(string s) { // 1、状态初始化 int len = s.size(); vector<int> minCut(len+1); for(int i = 0; i <= len; ++i) { minCut[i] = i-1; } // 2、状态转移 for(int i = 2; i <= len; ++i) { if(IsPal(s, 0, i-1)) { minCut[i] = 0; continue; } else { for(int j = 1; j < i; ++j) { if(IsPal(s, j, i-1)) { minCut[i] = min(minCut[i], minCut[j]+1); } } } } // 3、返回结果 return minCut[len]; } private: // 判断字符区间是否回文 bool IsPal(const string& s, int start, int end) { while(start < end) { if(s[start++] != s[end--]) { return false; } } return true; } };
性能分析：
时间复杂度：O(n^3)，n为字符串长度。在第二次for循环内每次都有判断是否回文的逻辑，所以实际上是3层for循环。
空间复杂度：O(n)。必须要保存前i个字符的最小分割结果。
优化时间复杂度为O(n^2)
上面的代码在第二层for循环中每次需要判断一段区间内的字符串是否回文，这样导致时间复杂度为O(n^3)，现在我们考虑用空间换时间的方法来优化时间复杂度为O(n ^2)。具体办法是使用一个二维数组来存储[i, j]范围内字符串的回文情况，到时候直接查找matrix[i][j]的值就知道是否回文了，矩阵的设计思路如下，也是用动态规划的思想：
目的：二维矩阵存储所有区间范围内的字符串回文情况。
状态定义：dp[i][j] = [i, j]范围内的字符串是否回文。
状态转移方程：dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true)
状态初始化：
i == j --> dp[i][j] = true
i+1 == j --> dp[i][j] = (s[i] == s[j] ? true : false)
PS：观察状态转移方程，在计算dp[i][j]时需要事先知道dp[i+1][j-1]的结果，所以我们从最后一行开始动态规划，又因为该矩阵的目的是存储字符串s所有区间范围内的字符串回文情况，所以只需计算矩阵主对角线上半部分的值即可：
最终代码如下：
class Solution { public: int minCut(string s) { // 1、状态初始化 int len = s.size(); vector<int> minCut(len+1); for(int i = 0; i <= len; ++i) { minCut[i] = i-1; } // 2、状态转移 vector<vector<bool>> matrix = GerMatrix(s); for(int i = 2; i <= len; ++i) { if(matrix[0][i-1]) { minCut[i] = 0; continue; } else { for(int j = 1; j < i; ++j) { if(matrix[j][i-1]) { minCut[i] = min(minCut[i], minCut[j]+1); } } } } // 3、返回结果 return minCut[len]; } private: vector<vector<bool>> GerMatrix(const string& s) { int n = s.size(); vector<vector<bool>> matrix(n, vector<bool>(n, false)); for(int i = n-1; i >= 0; --i) { for(int j = i; j < n; ++j) { if(i == j) matrix[i][j] = true; else if(i+1 == j && s[i] == s[j]) matrix[i][j] = true; else if(s[i] == s[j] && matrix[i+1][j-1]) matrix[i][j] = true; } } return matrix; } };
