理论基础
- 动态规划,英文:Dynamic Programming,简称DP,假如某一题目有很多重叠子题目,利用动态规划是最有用的。
- 所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。
- 动态规划是当前的效果取决于上一阶段的效果,因此存在一个递推公式
动态规划做题五部曲:
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 打印dp数组
如何debug:
- 找题目的最好方式就是把dp数组打印出来,看看毕竟是不是按照自己思绪推导的!
- 写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的效果。
- 思考以下题目:
- 是否举例推导状态转移公式?
- 是否打印dp数组的日记?
- dp数组打印效果与推导状态时同等?
斐波那契数
力扣链接
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,背面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请盘算 F(n) 。
动规五部曲:
- dp的定义: 第 i 个数的斐波那契数值是dp
- 确定递推公式: F(n) = F(n - 1) + F(n - 2)
- dp数组初始化: F(0) = 0,F(1) = 1
- 确定遍历顺序: 从递归公式dp = dp[i - 1] + dp[i - 2];中可以看出,dp是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历。
程序实现:
- int fib(int n)
- {
- if(n <= 1)
- return n;
- 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];
- }
复制代码 爬楼梯
力扣链接
假设你正在爬楼梯。需要 n ( n > 0)阶你才气到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种差别的方法可以爬到楼顶呢?
示例 1:
输入: 2
输出: 2
示例 2:
输入: 3
输出: 3
思绪:
- 那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层。
- 所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划
- 即要爬到第 i 层,可以由第 i - 1 层跨一步,或者 i - 2 层跨2步到达。
动态规划五部曲:
- dp的定义: 爬到第 i 层楼梯,有 dp 种方法
- 确定递推公式:
- 首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp了么。
- 另有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp了么
- 那么dp就是 dp[i - 1]与dp[i - 2]之和,即 dp = dp[i-1] + dp[i-2]
- dp数组初始化: dp[1] = 1; dp[2] = 2
- 确定遍历顺序: 从递推公式dp = dp[i - 1] + dp[i - 2]; 中可以看出,遍历顺序一定是从前向后遍历的。
- 举例推导dp数组
举例当n为5的时候,dp table(dp数组)应该是如许的
程序实现
- int climbStairs(int n)
- {
- if (n <= 2)
- 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];
- }
复制代码 利用最小花费爬楼梯
力扣链接
给定一个整数数组 cost ,其中 cost 是从楼梯第 i 个台阶向上爬需要付出的费用。一旦你付出此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯,盘算并返回达到楼梯顶部的最低花费
示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 付出 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
动态规划五部曲:
- dp的定义: 到达第 i 台阶所花费的最少体力为 dp
- 确定递推公式: 可以有两个途径得到dp,一个是dp[i-1] 一个是dp[i-2]。
- dp[i - 1] 跳到 dp 需要花费 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp 需要花费 dp[i - 2] + cost[i - 2]。
- 一定是选最小的,所以
- dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
复制代码
- dp数组初始化: 题意表明可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯,因此 dp[0] = 0,dp[1] = 0
- 确定遍历顺序: 因为是模拟台阶,而且 dp 由 dp[i-1] dp[i-2]推出,所以是从前到后遍历cost数组就可以了
- 举例推导dp数组
拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:
程序实现:
- int minCostClimbingStairs(vector<int>& cost)
- {
- if(cost.size() <= 1)
- return 0;
- int size = cost.size();
- vector<int> dp(size + 1); // 到达第 i 层的最小花费
- dp[0] = 0;
- dp[1] = 0;
- for(int i = 2; i <= size; i++)
- dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
- // for(int num : dp)
- // cout << num << " ";
- // cout << endl;
- return dp[size];
- }
复制代码 差别的路径
力扣链接
一个呆板人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )
呆板人每次只能向下或者向右移动一步。呆板人试图达到网格的右下角(在下图中标记为 “Finish” )。
问统共有多少条差别的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 2, n = 3
输出:3
思绪:
因为呆板人只能向下或者向右移动一格,因此对于 nums[j] 只能由上方一格 nums[i-1][j] 或者 左边一格 nums[j-1] 移动得到。
动态规划五部曲:
- dp[j]的定义: 从[0,0] 出发到 [i,j] 有 dp[j] 条差别的路径。
- 确定递推公式: 向下移动一格的路径 + 向右移动一格的路径(雷同爬楼梯)
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
复制代码 - dp数组初始化:
- 根据递推公式可以看,需要对第一行与第一列的数组初始化。
- 第一列的 dp 数组均为1,因为呆板人跳到第一列的任何格子的路径只有1条(一直向下),即 dp[0] = 1;
- 第一列的 dp 数组均为1,因为呆板人跳到第一行的任何格子的路径只有1条(一直向右),即 dp[0][j] = 1;
- 其余格子均通过递推公式求得,因此初始化为任何值均可。
- 因此为了简化程序,dp 数组全部初始化为 1 即可。
- vector<vector<int>> dp(m, vector<int>(n,1));
复制代码
- 确定遍历顺序: 根据递推公式,都是从其上方和左侧推导而来,因此从左到右,从上到下遍历即可。
- 举例推导dp数组
程序实现:
- int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n,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];}
复制代码 差别的路径2
力扣链接
一个呆板人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
呆板人每次只能向下或者向右移动一步。呆板人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条差别的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
本题在上一题-差别的路径的差别点上进行优化
差别点:
- 本题在递推时需要判断是否遇到障碍物,一旦遇到障碍物时,可走的路径为 0 (可省略,初始化就为0)
- if(obstacleGrid[i][j] == 0)
- dp[i][j] = 0; // 可省略 因为初始化就为 0
- else
- dp[i][j] = dp[i][j-1] + dp[i-1][j];
复制代码 - 在初始化时,第一行/列,在遇到障碍物前,可走路径为1,障碍物后的路径均为 0,不妨初始均为0,即包括第一行/列遇到障碍物后,同时包括递推时遇到障碍物。
- // 初始化程序优化
- vector<vector<int>> dp(m, vector<int>(n,0));
复制代码 - 初始化第一行 / 列 遇到障碍物前路径条数为 1
- // 第一列
- for(int i = 0; i < m; i++)
- {
- if(obstacleGrid[i][0])
- break;
- else
- dp[i][0] = 1;
- }
- // 第一行
- for(int j = 0; j < n; j++)
- {
- if(obstacleGrid[0][j])
- break;
- else
- dp[0][j] = 1;
- }
复制代码 程序实现:
- int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
- {
- int m = obstacleGrid.size();
- int n = obstacleGrid[0].size();
-
- // 初始化程序优化
- vector<vector<int>> dp(m, vector<int>(n,0));
- // 第一列
- for(int i = 0; i < m; i++)
- {
- if(obstacleGrid[i][0])
- break;
- else
- dp[i][0] = 1;
- }
- // 第一行
- for(int j = 0; j < n; j++)
- {
- if(obstacleGrid[0][j])
- break;
- else
- dp[0][j] = 1;
- }
-
- // 其他块
- for(int i = 1; i < m; i++)
- {
- for(int j = 1; j < n; j++)
- {
- if(obstacleGrid[i][j] == 0)
- dp[i][j] = 0;
- else
- dp[i][j] = dp[i][j-1] + dp[i-1][j];
- }
- }
- return dp[m-1][n-1];
- }
复制代码 整数拆分
力扣链接
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以得到的最大乘积。
示例 1:
输入: 2
输出: 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思绪
- 将n拆成2个数,i 和 n - i,乘积为 i * (n - i)
- 将n拆成多个数(>2),其中一个数为 i,另外数的和为 n - i,乘积为 i * dp[n-i],其中 dp[j] 表示拆分数字 j,可以得到最大的乘积
- 这里这个想法(dp的含义)其实不是特殊好想
动态五部曲
- dp的定义:拆分数字 i,可得到的最大乘积
- 递推公式:
- dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
复制代码 - dp数组初始化
- 严酷从 dp 的定义来说,dp[0] dp[1] 就不应该初始化,也就是没故意义的数值
- 这里只初始化 dp[2] = 1;
- 确定遍历顺序: 通过递推公式看出,从前向后遍历,先有dp[i - j]再有dp,所以顺序为:
- for (int i = 3; i <= n ; i++) { for (int j = 1; j < i - 1; j++) { dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- }}
复制代码- 举例推导dp数组: 举例当n为10 的时候,dp数组里的数值,如下:
程序实现:
- int integerBreak(int n) { // dp[i] : i 拆分后得到的最大乘积数 vector<int> dp(n+1); // dp[0] dp[1] 偶然义 dp[0] = dp[1] = 0; dp[2] = 1; for(int i = 3; i <= n; i++) { // 对 i 进行拆分 j 和 i-j for(int j = 1; j < i; j++) { dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- } } return dp[n];}
复制代码 差别的二叉搜索树
力扣链接
给定一个整数 n,求以 1 … n 为节点构成的二叉搜索树有多少种?
示例:
突破口:无
思绪,画图找规律
当 n = 3 时,可以分为以下几种情况:
- 当 1 为头结点的时候,其右子树有两个节点,和 n 为 2 的时候两棵树的布局是一样的啊!
- 当 3 为头结点的时候,其左子树有两个节点,和 n 为 2 的时候两棵树的布局也一样
- 当 2 为头结点的时候,其左右子树都只有一个节点,和 n 为 1 的时候只有一棵树的布局也是一样的!
致此,发现了重叠子题目,也就是可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
如图所示:
此时我们已经找到递推关系了,那么可以用动规五部曲再体系分析一遍。
- dp含义: 1 到 i 为节点构成的二叉搜索树的个数为dp。
- 确定递推公式: dp += dp[ 以j为头结点左子树节点数量 ] * dp[ 以j为头结点右子树节点数量 ],j相称于是头结点的元素,从1遍历到i为止。所以递推公式:
- dp[i] += dp[j - 1] * dp[i - j];
复制代码 j-1 为 j 为头结点左子树节点数量,i-j 为以 j 为头结点右子树节点数量
- dp数组初始化:
- 确定遍历顺序: 通过递推公式看出,节点 i 依靠 i 之前节点数的状态,所以为顺序遍历。
- for(int i = 2; i <= n; i++)
- {
- for(int j = 1; j <= i; j++)
- {
- dp[i] += dp[j-1] * dp[i-j];
- }
- }
复制代码 - 举例推导dp数组: n为5时候的dp数组状态如图:
程序实现:
- int numTrees(int n) { // dp[i] : 输入 i 能形成的最多二叉搜索树的个数 vector<int> dp(n+1); dp[0] = 1; dp[1] = 1;
- for(int i = 2; i <= n; i++) { for(int j = 1; j <= i; j++) { dp[i] += dp[j-1] * dp[i-j]; } } for(int num: dp) cout << num << " "; return dp[n];}
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |