一、动态规划总结
1.1 题目
一维
- 斐波那契数列
- 70.爬楼梯
- 413.等差数列划分
- 吃烧饼
- 343.整数拆分
二维
- 64.最小路径和
- 62.不同路径
子序列问题
- 53.最大连续子序和
- 300.最长上升子序列
- 650.只有两个键的键盘
两个字符串
- 1143.最长公共子序列
- 72.编辑距离（hard）
- 10.正则表达式匹配（hard）
1.2 解题思路
题目特征：求某个问题的最优解，并且该问题可以分为多个子问题，子问题之间还有重叠的更小子问题。
思路：
- 用自上而下的递归思想去分析问题，找到状态转移方程。
- 用自下而上的循环递推实现，使用dp数组保存子问题的最优解。
二、动态规划题目
斐波那契数列
题目描述：公式为：f(n) = f(n-1) + f(n-2) ，如：112358...
方法1：递归
int fib(int n){
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
}
递归树
方法2：动态规划
思路：因为递归有很多重复的计算，所以用数组将子步骤计算的结果都保存下来。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
int fib2(int n){
vector<int> dp(n+1, 0);
dp[1] = 1;
dp[2] = 1;
for (int i=3; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
方法3：状态压缩
思路：因为计算f(n)，只用到了前两个数，所以可以用两个变量来替代dp数组。
int fib3(int n){
int f_2 = 1;
int f_1 = 1;
int res;
for (int i=3; i<=n; i++) {
res = f_1 + f_2;
f_2 = f_1;
f_1 = res;
}
return res;
}
70.爬楼梯
问题描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
解答：基本上是斐波那契数列换了一种问法，数组前几位稍有区别 -> 12358
int climbStairs(int n) {
int f_2 = 1;
int f_1 = 1;
int res = 0;
for (int i=2; i<=n; i++) {
res = f_2 + f_1;
f_2 = f_1;
f_1 = res;
}
return res;
}
413. 等差数列划分
思路：dp[i]表示以nums[i]结尾的等差数列的个数。
结果等于dp数组的总和
int numberOfArithmeticSlices(vector<int>& A) {
vector<int> dp(A.size(), 0);
for (int i=2; i<A.size(); i++) {
if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
dp[i] = dp[i-1] + 1;
}
}
int sum = accumulate(dp.begin(), dp.end(), 0);
return sum;
}
吃烧饼
一个烧饼行举办吃烧饼大赛，共n个盘子，第i个盘子有Si个烧饼；
参赛者每次选择1到n中的某个整数x，将1到x盘子中的烧饼吃掉一个，如果Si为0，则无法吃i之后的盘子，问第一个参赛者最多吃多少个烧饼？
思路1：贪心算法
int maxAns(int n, vector<int> nums){
int ans = 0;
int endInx = n-1;
while (endInx >= 0) {
for (int i=0; i<=endInx; i++) {
if (nums[i] == 0) {
endInx = i-1;
continue;
}
ans++;
nums[i]--;
}
}
return ans;
}
思路2：动态规划
状态转移方程：dp[i] = min(dp[i-1], nums[i]);
结果等于dp数组的和。
int maxAns2(int n, vector<int> nums){
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
for (int i=1; i<nums.size(); i++) {
dp[i] = min(dp[i-1], nums[i]);
}
return accumulate(dp.begin(), dp.end(), 0);
}
343.整数拆分
思路：
状态定义：dp[i]保存着整数i拆分后的最大乘积，
状态转移方程：dp[n] = max(dp[i] * dp[n-i]) i=1..n/2
注意：前三个数字dp[1]、dp[2]、dp[3]较为特殊
- dp[1]是因为从2开始才能切分，
- dp[2]和dp[3]的数字本身比它拆分后的还要大
int integerBreak(int n) {
if (n<2) return 0;
if (n==2) return 1;
if (n==3) return 2;
vector<int> dp(n+1,0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i=4; i<=n; i++) {
int tempMax = 0;
for (int j=1; j<=i/2; j++) {
tempMax = max(tempMax, dp[j] * dp[i-j]);
}
dp[i] = tempMax;
}
return dp[n];
}
64.最小路径和
状态定义：dp[i][j] 是到达 i, j 的最小路径和
状态转移方程：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
注意：第一行和第一列需要特殊处理一下。
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
if (i-1 == 0) {
dp[i][j] = dp[i][j-1];
}else if(j-1 == 0){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
}
dp[i][j] += grid[i-1][j-1];
}
}
return dp[m][n];
}
62.不同路径
思路1：DFS。超时。
int dfs(int row, int col, int m, int n){
if (row>m || col>n) return 0;
if (row == m && col == n) return 1;
return dfs(row+1, col, m, n) + dfs(row, col+1, m, n);
}
int uniquePaths2(int m, int n){
return dfs(1, 1, m, 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。
int uniquePaths(int m, int n){
vector<vector<int>> dp(m+1, vector<int>(n+1, 1));
for (int i=2; i<=m; i++) {
for (int j=2; j<=n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
53.最大连续子序和
思路：
状态定义：dp[i]表示已数字nums[i]结尾的连续子数组的最大子序和。
状态转移方程：
- 如果当前节点加上dp[i-1]，比它自身还小，则
dp[i] = nums[i]； - 否则：
dp[i] = nums[i] + dp[i-1]。
遍历过程中，使用一个变量记录状态数组的最大值。
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int max = dp[0];
for (int i=1; i<nums.size(); i++) {
int temp = dp[i-1] + nums[i];
if (temp < nums[i]) {
dp[i] = nums[i];
}else{
dp[i] = temp;
}
max = max < dp[i] ? dp[i] : max;
}
return max;
}
状态压缩：dp[i]只与dp[i-1]有关，所以dp数组可以压缩为一个变量
int maxSubArray(vector<int>& nums) {
int dp_i_1 = nums[0];
int ans = dp_i_1;
for (int i=1; i<nums.size(); i++) {
int temp = dp_i_1 + nums[i];
if (temp < nums[i]) {
dp_i_1 = nums[i];
}else{
dp_i_1 += nums[i];
}
ans = max(dp_i_1, ans);
}
return ans;
}
300.最长上升子序列
思路：
状态定义：dp[i]保存以当前元素为尾节点的最长上升子序列的长度。
状态转移方程：从后往前比较，找到比它小且dp[j]最大的元素，然后 dp[i]=dp[j]+1
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> dp(nums.size(),0);
dp[0] = 1;
int res = 1;
for (int i=1; i<nums.size(); i++) {
int prevIdx = -1;
int prevDp = 0;
for (int j=i-1; j>=0; j--) {
if (nums[j] < nums[i] && dp[j] > prevDp){
prevDp = dp[j];
prevIdx = j;
}
}
if (prevIdx < 0) dp[i] = 1;
else dp[i] = dp[prevIdx] + 1;
res = max(res, dp[i]);
}
return res;
}
650.只有两个键的键盘
思路：dp[i]表示需要操作多少步才能得到
状态转移方程：
- 如果这个数有因子，则dp[i] = dp[j] + dp[i/j];
- 如果是素数，则dp[i] = i;
int minSteps(int n) {
vector<int> dp(n+1, 0);
for (int i=2; i<=n; i++) {
dp[i] = i;
for (int j=2; j<=n/2; j++) {
if (i%j == 0) {
dp[i] = dp[j] + dp[i/j];
break;
}
}
}
return dp[n];
}
1143.最长公共子序列
题目描述：公共子序列可以不连续。
思路：
状态定义：dp[i][j]保存着当前元素为尾节点的最长公共子序列长度
状态转移方程：
- 如果当前text1[i]，text2[j]相等，
dp[i][j] = dp[i-1][j-1] + 1 - 如果当前text1[i]，text2[j]不相等，
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
以"acbcbcef"和"abcbced"为例，动态规划数组如下图所示：
该图是公共子序列连续的情况：
- 如果当前text1[i]，text2[j]不相等，
dp[i][j] = 0；
在该题中公共子序列可以不连续的情况：
- 如果当前text1[i]，text2[j]不相等，
dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
int longestCommonSubsequence(string text1, string text2) {
int rows = text1.size();
int cols = text2.size();
// 多使用一行和一列
vector<int> d(cols+1, 0);
vector<vector<int>> dp(rows+1, d);
for (int i=1; i<=rows; i++) {
for (int j=1; j<=cols; j++) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[rows][cols];
}
72. 编辑距离
题目描述：将 word1 转换成 word2 所使用的最少操作数 。
例子1：penumu 和 u
例子2：zoo 和 zo
思路：除了基本的动态规划思路之外，多使用一行和一列来辅助计算，这很重要！
可以对数组进行统一计算，且对特殊情况（如某一方为""）也适用。
状态转移方程：
- 如果word1[i]、word2[j]相等，
dp[i][j] = dp[i-1][j-1] - 如果word1[i]、word2[j]不相等，
dp[i][j] = min(dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]) + 1
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 边界，第0行 和 第0列
for (int i=0; i<=m; i++) dp[i][0] = i;
for (int j=0; j<=n; j++) dp[0][j] = j;
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))+1;
}
}
}
return dp[m][n];
}
10.正则表达式匹配
思路：
状态定义：dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
状态转移方程：
1. p[j] == s[i]: dp[i][j] = dp[i-1][j-1]
2. p[j] == ".": dp[i][j] = dp[i-1][j-1]
3. p[j] ==" * ":（考虑他前面的元素 p[j-1]）
前一个字符匹配不上的情况，如(ab, abc * )，此时*匹配零个
1. p[j-1] !=s[i] && p[j-1] == '.'：dp[i][j] = dp[i][j-2]
前一个字符能匹配 s[i]
2. p[j-1] == s[i] or p[j-1] == '.'：
dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
dp[i][j-2] // 匹配0个
dp[i][j-1] // 匹配1个
dp[i-1][j] // 匹配多个
例子1："###bbb" 和 "###b*"（匹配1个 和 匹配多个）
例子2: "ab" 和 ".*.."（匹配0个）
例子3: "abbbbc" 和 "ab*d*c"
bool isMatch(string s, string p) {
s=" "+s;//防止该案例：""\n"c*"
p=" "+p;
int m=s.size(), n=p.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
dp[0][0]=true;
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
if (s[i-1] == p[j-1]) dp[i][j] = dp[i-1][j-1];
else if (p[j-1] == '.') dp[i][j] = dp[i-1][j-1];
else if (p[j-1] == '*'){
if (p[j-2] != s[i-1] && p[j-2] != '.') {
dp[i][j] = dp[i][j-2];
}else{
dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
}
}
}
}
return dp[m][n];
}
网友评论