国内房地产设计网站建设,网站如何备案工信局,网页制作工具程,svn教程图文详解 - 青岛网站建设动态规划特点
动态规划中每一个状态一定是由上一个状态推导出来#xff0c;根据这个特点#xff0c;可以在状态计算过程中#xff0c;存储某一条件下的数据#xff0c;当再次遍历该条件时#xff0c;直接取该条件对应的数据即可#xff0c;可以避免重复计算#xff0c;…动态规划特点
动态规划中每一个状态一定是由上一个状态推导出来根据这个特点可以在状态计算过程中存储某一条件下的数据当再次遍历该条件时直接取该条件对应的数据即可可以避免重复计算减少时间。
解题步骤动态规划五步曲
1确定dp数组dp table以及下标的含义 2确定递推公式 3dp数组如何初始化 4确定遍历顺序 5举例推导dp数组
1、动态规划基础题
dp[i] dp[i - 1] dp[i - 2] 144、【动态规划】leetcode ——509. 斐波那契数递归法迭代法C版本优化方法是让dp[1]始终指向最后dp[0]指向前一位用sum作为中间临时变量
爬楼梯两道 dp[i] dp[i - 1] dp[i - 2] 145、【动态规划】leetcode ——70. 爬楼梯暴力法动态规划C版本爬到第i阶楼梯可以依托于爬第i - 1阶楼梯的方式或依托于爬到第i - 2阶楼梯的方式。 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i -2]) 146、【动态规划】leetcode ——746. 使用最小花费爬楼梯递归法迭代法C版本注意分清到第i层并不花费第i层的费用只有跳到第i 1层或第i 2层才花费。找到跳到该层之前的最小费用方案。
机器人运动路径两道 dp[i][j] d[i - 1][j] dp[i][j - 1] 147、【动态规划】leetcode ——62. 不同路径递归法迭代法C版本到达i,j可以从i-1,j或i,j-1两个位置到达依托于这两个位置上的可到达路径再加上这条路径到达i,j。 dp[i][j] dp[i - 1][j] dp[i][j - 1] 148、【动态规划】leetcode ——63. 不同路径 II递归法迭代法C版本与上面的相比多一个条件判定只统计没有障碍物的位置对于到达有障碍物的位置不统计。
拆分数字 dp[i] max(d[i], max(j * (i - j), j * dp[i - j])) 149、【动态规划】leetcode ——343. 整数拆分C版本d[i[表示数字i拆分后可得到的乘积最大值找到分成两个j * (i - j)和分成三个及以上j * dp[i - j]中的最大值再和之前已得到的dp[i]相比求出当前乘积最大值。 dp[i] dp[j - 1] * dp[i - j] 150、【动态规划】leetcode ——96. 不同的二叉搜索树C版本以i为根节点构造的BST个数 以j - 1为根节点的个数 * 以i - j为根节点的个数再让j从0到i的各种情况求和。
2、背包问题
背包问题是在规定背包容量为j的前提下每个物品对应的体积为v[i]价值为w[i]从物品0到物品i中选择物品放入背包中找出符合某种要求的价值。
1背包问题种类
01背包每种物品只能选择1个。完全背包每种物品可以选择无限个。多重背包每种物品最多可选s[i]个。
2递推公式
01背包dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])完全背包dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i])多重背包dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i], dp[i - 1][j - 2*v[i]] w[i] ... dp[i - 1][j - s[i]*v[i]] s[i]*w[i])
3滚动数组遍历顺序
01背包从大到小完全背包从小到大多重背包在01背包的基础上从大到小多一层for循环选物品个数
详细内容【动态规划】背包问题题型及方法归纳
3、打家劫舍问题 dp[i] max(dp[i - 1], dp[i - 2] nums[i]) 163、【动态规划】leetcode ——198. 打家劫舍C版本不选当前而选择前一个i-1物品选择当前物品i之间找最大值。 dp[i] max(dp[i - 1], dp[i - 2] nums[i])分别对两个范围的数组进行dp更新求最大值 163、【动态规划】leetcode ——213. 打家劫舍 II环形列表线性化C版本将环形列表线性化分成两种情况求二者中的最大值。 树形dpmax(偷当前结点 不偷当前结点) 165、【动态规划】leetcode ——337. 打家劫舍 III记忆化递归动态规划C版本树形dp需采用后序遍历每次返回值为一个二维数组0不偷1偷分别遍历左和右子树然后将偷当前结点的结果与不偷当前结点的结果对比取二者中的最大值。
4、股票问题
1仅能进行一次和无限次的买卖股票
设置两个dpdp[i][0]表示持有股票时具有的最大收益dp[i][1]表示不持有股票时具有的最大收益。
模板
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n 1, vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i n; i) {// 仅能进行一次买卖操作// dp[i][0] max(dp[i - 1][0], - prices[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[n - 1][1];}
}; 持有dp[i][0] max(dp[i-1][0], -prices[i])、不持有dp[i][1] max(dp[i-1], dp[i][0] prices[i]) 168、【贪心算法】leetcode ——121. 买卖股票的最佳时机dp数组变量优化 C版本仅允许进行一次买卖 持有dp[i][0] max(dp[i-1][0], dp[i][1] - prices[i])、不持有dp[i][1] max(dp[i-1], dp[i][0] prices[i]) 130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II贪心算法C版本可以进行多次买卖 持有dp[i][0] max(dp[i-1][0], dp[i][1] - prices[i])、不持有dp[i][1] max(dp[i-1], dp[i][0] prices[i] - fee) 172、【动态规划】leetcode ——714. 买卖股票的最佳时机含手续费 C版本相比于2多了一个扣除手续费。
2可以进行有限次的买卖股票
模板
class Solution {
public:int maxProfit(int k, vectorint prices) {if(prices.empty() || prices.size() 1) return 0;int n prices.size();vectorvectorint dp(n 1, vectorint(2 * k 1));// dp[0][0] 0for(int i 1; i 2 * k 1; i 2) {dp[0][i] -prices[0]; // 2*k-1为持有为-prices[0]2*k为不持有为0。}for(int i 1; i n; i) {for(int j 1; j 2 * k 1; j 2) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] prices[i]);}}return dp[n - 1][2 * k];}
}; 第一次持有dp[i][1] max(dp[i - 1][1], -prices[i])第一次不持有dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i])第二次持有dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]), 第二次不持有dp[i][4] max(dp[i - 1][4], dp[i-1][3] prices[i]) 169、【贪心算法】leetcode ——123. 买卖股票的最佳时机 III二维数组一维数组 C版本可以进行两次买卖 第k次持有dp[i][2 * k - 1] max(dp[i - 1][2 * k - 1], dp[i - 1][2 * k - 2] - prices[i])第k次不持有dp[i][2 * k] max(dp[i - 1][2 * k], dp[i - 1][2 * k - 1] prices[i]) 170、【贪心算法】leetcode ——188. 买卖股票的最佳时机 IV二维数组一维数组 C版本可以进行k次买卖
3含有冷冻期可以进行有限次的买卖股票
持有股票dp[i][0] max(dp[i - 1][0], dp[i - 1][2] - prices[i])、不持有股票且明天将为冷冻期dp[i][1] dp[i][0] prices[i]、不持有股票且明天不为冷冻期dp[i][2] max(dp[i - 1][2], dp[i - 1][1]) 171、【动态规划】leetcode ——309. 最佳买卖股票时机含冷冻期 C版本
5、子序列问题
1递增子序列问题 dp[i] max(dp[i], dp[j]1) 173、【动态规划】leetcode ——300. 最长递增子序列 C版本按顺序遍历当对比发现当前元素大于前方某一位置元素时就在该位置元素已有的最长递增子序列长度上加一和当前元素已记录的最长递增子序列长度对比最大值。 dp[i] dp[i -1] 1 174、【动态规划/贪心算法】leetcode ——674. 最长连续递增序列 C版本每遇到一个连续递增子序列就在前一个的基础上加一。
2编辑距离 dp[i][j] dp[i - 1][j - 1] 1 175、【动态规划】leetcode ——718. 最长重复子数组 C版本比较到nums1[i -1]与nums2[j - 1]相等时在前一个的基础上加一。 当text1[i - 1] text2[j - 1]时令dp[i][j] dp[i - 1][j - 1] 1当不等于时dp[i][j] max(dp[i][j - 1], dp[i - 1][j]) 176、【动态规划】leetcode ——1143. 最长公共子序列C版本与1的区别在于2中不要求子序列连续。 拓展题 177、【动态规划】leetcode ——1143. 最长公共子序列C版本注意问题转化。 dp[i] max(dp[i] nums[i], nums[i]) 129、【动态规划/贪心算法】leetcode ——53. 最大子数组和C版本当前的加上之前的和从当前情况重新开始二者之间取最大值。 当text1[i - 1] text2[j - 1]时令dp[i][j] dp[i - 1][j - 1] 1当不等于时dp[i][j] dp[i][j - 1] 178、【数组/动态规划】leetcode ——392. 判断子序列双指针动态规划C版本思路与2的区别在于遇到不等时固定子串整体串前移一个 当s[i - 1] t[j - 1]时令dp[i][j] dp[i - 1][j - 1] dp[i-1]dp[j]当不等于时dp[i][j] dp[i][j - 1] 178、【动态规划】leetcode ——115. 不同的子序列C版本与5中不同的在于此时要进行累计因此需要再加上t维持不动s缩一个的情况。 思路一当word1[i - 1] word2[j - 1]时令dp[i][j] dp[i - 1][j - 1]当不等于时dp[i][j] min(dp[i][j - 1] 1, dp[i - 1][j] 1) 思路二在求最长公共子序列的基础上得到长度也能搞两个序列总长度减去二倍的最长公共子序列长度。 180、【动态规划】leetcode ——583. 两个字符串的删除操作两种动态规划思路C版本 相等dp[i][j] dp[i - 1][j - 1]不相等1增dp[i][j - 1] 12删dp[i - 1][j] 13改dp[i - 1][j - 1] 1 181、【动态规划】leetcode ——72. 编辑距离C版本主要是两个状态四个操作相等时对应状态一种操作不相等时对应状态三种操作。
3回文串 当s[i]s[j]时若j - i 1则dp[i][j]true若j - i 1且dp[i-1][j1]true则dp[i][j]true否则为false。当s[i]!s[j]时则dp[i][j]false 182、【动态规划/数组】leetcode ——647. 回文子串动态规划双指针C版本每次判定两段然后基于长度情况和上一次结果的进行判定。 当s[i]s[j]时dp[i][j]dp[i1][j-1]2当s[i]!s[j]时dp[i][j]max(dp[i][j-1],dp[i1][j])。 182、【动态规划】leetcode ——516. 最长回文子序列C版本
