二刷 动态规划

什么是动态规划 Dynamic Programming DP

如果某一问题有很多重叠子问题，使用动态规划时最有效的

动态规划中每一个状态是由上一个状态推导出来的。

动规五部曲

1.确定dp数组以及下标的含义

2.确定递归公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

509.斐波那契数

1.确定dp数组和下标的含义

dp[i]:第i个数的斐波那契数值是dp[i]

2.确定递推公式

dp[i] = dp[i-1]+dp-i-2

3.dp数组如何初始化

dp[0] = 0;

dp[1]=  1

4.确定遍历顺序

dp[i]依赖dp[i-1],dp[i-2]，因此是从前向后

5.举例推导

0 1 1 2 3 5 8 13

class Solution {
public:int fib(int n) {//如果是0,1,直接返回if(n <= 1) return n;//创建dp数组vector<int> dp(n+1);//初始化dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

• 输入： 2
• 输出： 2
• 解释： 有两种方法可以爬到楼顶。
  • 1 阶 + 1 阶
  • 2 阶

1.确定dp数组及下标含义

dp[i]:爬上i楼有dp[i]种方法

2.确定递推公式

第一层有一种方法

第二层有两种方法

第一层跨两步到第三层；第二层跨一步到第三层；

所以第三层楼梯的状态可以由第二层楼梯和到第一层楼梯的状态推导出来

dp[i-1]，上i-1层楼梯，有dp[i-1]种方法，再一步跳一个台阶到dp[i]

dp[i-2]，上i-2层楼梯，有dp[i-2]种方法，再一步跳两个台阶就是dp[i]。

dp = dp[i-1]+dp[i-2]

3.dp数组初始化

dp[1] = 1

dp[2] = 2

4.确定遍历顺序

从前向后

5.模拟

class Solution {
public:int climbStairs(int n) {if ( n <= 1) return n;vector<int> dp(n+1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1.确定dp数组和下标含义

dp[i]:到达i楼层的最低花费是dp[i]

2.确定递推公式

dp[i] = dp[i-1] + cost[i -1]

dp[i] = dp[i-2] + cost[i -2]

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);

3.初始化

到达第0和第1台阶不需要花费体力

dp[0] = 0;

dp[1] = 0;

4.遍历顺序

从前向后

5.模拟

此处的n是cost.size(）

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min (dp[i-1] + cost[i - 1], dp[i-2] + cost[i - 2]);}return dp[cost.size()];}
};

62.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

机器人从00出发到m-1,n-1

1.确定dp数组和下标含义

dp[i][j]：从00出发到ij有dp[i][j]条不同的路径

2.确定递推公式

只有两个方向能来

dp[i][j] = dp[i-1][j] + dp[i][j-1];

3.初始化

for  dp[i][0] = 1

for  dp[0][j] = 1

4.遍历顺序

从左到右一层一层遍历

注意最后一个点是m-1，n-1

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for(int i = 0; i < m; i++) dp[i][0] = 1;for(int j = 0; j < n; j++) dp[0][j] = 1;//双层循环for(int i = 1; i < m; i++) {for (int j = 1; j < n; j++){dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}return dp[m - 1][n - 1];}
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

思路：

1.确定dp数组和下标含义

dp[i][j]:从00到m-1,n-1有dp[i-1][j-1]条路径

2.确定递推公式

没有障碍情况下

if（obstacleGrid[i][j] == 0）

dp[i][j] = dp[i-1][j] + dp[i][j-1]

3.确定初始化

没有障碍才能为1

4.左上到右下

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();//起点或终点有障碍物,直接返回0;if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化，没有障碍物才能为1，遇到障碍物就为0for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1; //遍历，遇到障碍物就跳过for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

• 输入: 2
• 输出: 1
• 解释: 2 = 1 + 1, 1 × 1 = 1。

1.确定dp数组和下标的含义

dp[i]:正整数i划分后得到的最大乘积

2.确定递推公式

从1遍历j，

将i划分为两个数 ：dp = j*(i-j)

继续划分：j*dp[i-j]

dp[i] = max({dp[i], j*(i-j),j*dp[i-j]})

3.初始化

dp[2] = 1

4.递归顺序

从前向后

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;for (int i = 3; i <= n; i++) {//i/2：一般乘积最大 是中间的数for (int j = 1; j <= i/2; j++) {//j * (i-j)表示分成两个数字；j*dp[i - j]表示分成两个以上数字dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};

96.不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

1.确定dp[i]数组及下标的含义

dp[i]:以1-i为节点组成的二叉搜索树由dp[i]种

2.确定递推公式

n=3时

元素1为头节点搜索树的数量 = 右子树有2个元素的搜索树数量*左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量*左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量*左子树有2个元素的搜索树数量

有两个元素的搜索树数量是dp[2]

有1个元素的搜索树数量是dp[1]

有0个元素的搜索树数量是dp[0]

dp[3] = dp[2]*dp[0] + dp[1]*dp[1]+dp[0]*dp[2]

dp[i] += dp[以j为头结点左子树节点数量]*dp[以j为头结点右子树节点数量]

j相当于头节点的元素，从1遍历到i为止

递推公式：dp[i] += dp[j - 1]*dp[i-j]

3.初始化

dp[0] = 1;

4.遍历顺序

i是依靠i之前的节点数的状态

for(int i = 1; i<=n; i++) {

        for (int j = 1;j <= i;j++) {

                dp[i] += dp[j - 1]* dp[i-j] }

}

5.模拟

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例 1：
• 输入：[1,2,3,1]
• 输出：4

1.确定dp[i]数组及下标的含义

dp[i]:考虑下标i以内的房屋，偷窃的最高金额

2.确定递推公式

如果偷第i间房，找出i-2以内的房屋最多可偷的金额+这间房的金额：dp[i] = dp[i - 2] + nums[i]

如果不偷第i间房，则可以考虑第i-1间房，但不一定就要偷i-1：dp[i] = dp[i-1]

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.初始化

dp[0] = nums[0];

dp[1] = max(nums[0], nums[0]);

4.遍历顺序

从前往后

注意要当nums只有一个时，直接返回这个即可。

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

• 输入：nums = [2,3,2]

• 输出：3

1.确定dp数组和下标的含义

dp[i]:i房屋以内的房屋最大的偷窃金额是dp[i]

2.确定递推公式

考虑两种情况:只包含头和只包含尾分别考虑，取最大值

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2);int result2 = robRange(nums, 1, nums.size() - 1);return max (result1, result2);}int robRange(vector<int>& nums, int start, int end) {vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];
}
};

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

• 示例 1：

• 输入：[7,1,5,3,6,4]

• 输出：5

1.确定dp[i]及下标的含义

dp[i][0]:第i天不持有股票

dp[i][1]:第i天持有股票

2.递推公式

dp[i][0]:第i天不持有股票有两种情况

第i-1天就不持有：dp[i - 1][0]

第i-1天持有，第i天卖出：dp[i - 1][1] + prices[i]

求最大值

dp[i][1]：第i天持有股票有两种情况

第i-1天就持有：dp[i - 1][1]

第i-1天不持有，第i天买入:- prices[i]

---这里 只买一次，第一次买股票 手头现金一定是0，所以直接-prices[i]

求最大值

3.初始化

dp[0][0] = 0

dp[0][1] = -prices[0]

4.遍历顺序

5.模拟

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(-prices[i], dp[i - 1][1]);}//最后一定是选择不持有股票赚的多return dp[prices.size() - 1][0];}
};

122.买卖股票的最佳时机II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1:

• 输入: [7,1,5,3,6,4]

• 输出: 7

1.确定dp[i]数组及下标的含义

dp[i][0]:不持有股票

dp[i][1]:持有股票

2.确定递推公式

dp[i][0]:第i天不持有股票

第i-1天就不持有，dp[i-1][0]

第i-1天持有，第i天卖出：dp[i - 1][1] + prices[i]

dp[i][1]:第i天持有股票

第i-1天就持有：dp[i-1][1]

第i-1天不持有,第i天买入：dp[i - 1][0] -prices[i]

唯一不同点：买卖多次股票，买入的时候手头现金非0

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[len - 1][0];}
};

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

• 输入："abc"
• 输出：3
• 解释：三个回文子串: "a", "b", "c"

1.确定dp[i]及下标的含义

dp[i][j]:[i,j]区间内是否是回文串

2.递推公式

s[i]==s[j]分为三种情况

a, aa都属于i-j<=1,相差一个距离

相差多个距离ababa，要根据dp[i+1][j-1]是否满足回文串了

3.初始化

初始都为false

4.遍历顺序

因为dp[i][j]依赖于dp[i+1][j-1] 所以从下往上从左往右

class Solution {
public:int countSubstrings(string s) {int len = s.size();int result = 0;vector<vector<bool>> dp(len, vector<bool>(len, false));for (int i = len - 1; i >= 0; i--) {for (int j = i; j < len; j++) {//j从i开始if (s[i] == s[j]) {if (j - i <= 1) {result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) {result++;dp[i][j] = true; }}}}return  result;}
};

516.最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

回文子序列不连续

1.确定dp[i]数组和下标

dp[i][j]：字符串s在[i,j]范围里最长的回文子序列的长度是dp[i][j]

2.确定递推公式

如果s[i] == s[j] ，dp[i][j] = dp[i+1][j-1]+2

如果s[i] != s[j]， dp[i][j] = max(dp[i+1][j], dp[i][j-1])；看看分别加入s[i]、s[j]哪一个可以组成最长的回文子序列。

3.初始化

i=j相同的时候，初始化为1

其他默认为0

4.遍历顺序

dp[i][j]依赖于dp[i+1][j-1]，从下往上，从左往右

内层循环：for(j = i+1)原因是，j必须大于i，并且j=i已经初始化了

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//i=j的时候,为1for(int i = 0; i < s.size(); i++) dp[i][i] =1;for(int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;}else if (s[i] != s[j]) {dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][s.size() - 1];}
};