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