动态规划经典例题
一、问题背景二、问题求解题型1：子序列问题1143. 最长公共子序列0072. 编辑距离 (比较经典的hard) — 需要在理解上边的题目1143 前提下0300. 最长递增子序列 —可以对比 674.最长连续递增序列（easy 贪心和dp都行）-- 滴滴面试遇到0673. 最长递增子序列的个数0139. 单词拆分
题型2：背包问题题型3：打家劫舍问题题型4：股票问题
一、问题背景
动态规划是一个对我而言比较复杂的一个问题，于是我想在这记录下我平时遇到过的动态规划的题目，以及总结其解体的通用思路。
二、问题求解
看到了有博主总结的dp的解题思路，我在这里分享给大家：
确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历的顺序举例尝试推导dp数组
以下是leetcode中的相关的例子
题型1：子序列问题
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 实例： 输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace” ，它的长度为 3 。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length();
int len2 = text2.length();
vector
for (int i=1; i for (int j=1; 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]); /* if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > result) result = dp[i][j]; */ } } return dp[len1][len2]; } }; 也可以压缩用一维数组求解： class Solution { public: int findLength(vector vector int result = 0; for (int i = 1; i <= A.size(); i++) { for (int j = B.size(); j > 0; j--) { if (A[i - 1] == B[j - 1]) { dp[j] = dp[j - 1] + 1; } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作 if (dp[j] > result) result = dp[j]; } } return result; } }; 0072. 编辑距离 (比较经典的hard) — 需要在理解上边的题目1143 前提下 这题是有点难度的可以自己去找下相关的资料进行理解 //(v)\\ 理解资料 — 代码随想录 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： · 插入一个字符 · 删除一个字符 · 替换一个字符 示例： 输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’) class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector 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-1], dp[i-1][j], dp[i][j-1]}) + 1; } } } return dp[m][n]; } }; 0300. 最长递增子序列 —可以对比 674.最长连续递增序列（easy 贪心和dp都行）-- 滴滴面试遇到 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 这里的dp数组初始化为1，因为至少连续递增子序列都是为1大小的（nums不为空的情况），其次我们的dp数组表达的含义是在dp[i]表示数组0-i位置中最长的递增子序列的长度。if (nums[i] class Solution { public: int lengthOfLIS(vector vector for (int j=1; j for (int i=0; i if (nums[j]>nums[i]) dp[j] = max(dp[i]+1, dp[j]); } } return *max_element(dp.begin(), dp.end()); } }; 0673. 最长递增子序列的个数 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。 示例： 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 这道题目本质上与上一道题是十分类似的，我们首先需要知道的是最长的递增子序列是多少，然后我们除了dp1数组保存最长的子序列长度外，还需要用一个数组dp2来保存一个最长递增子序列中可能存在几种情况，就比如[1,3,5,4,7]中，以7结尾的能够构成一个长度为4的最长子序列，但是其中有两种的构成方法，[1,3,5,7] 和 [1,3,4,7]，此时的dp1是为[1,2,3,3,4]，其实就是计算值为3的个数。 class Solution { public: int findNumberOfLIS(vector int length = nums.size(); if (length<=1) return length; vector vector int ans = 0; int maxLength = 1; for (int j=1; j for (int i=0; i if (nums[j]>nums[i]) { if (dp[i]+1 > dp[j]) { cnt[j] = cnt[i]; } else if (dp[i]+1 == dp[j]) { cnt[j] += cnt[i]; } dp[j] = max(dp[i]+1, dp[j]); } } if (dp[j]>maxLength) maxLength = dp[j]; } for (int i=0; i if (maxLength == dp[i]) ans += cnt[i]; } return ans; } }; 0139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。 class Solution { public: bool wordBreak(string s, vector vector unordered_set dp[0] = true; for (int i=1; i<=s.size(); i++) { for (int j=0; j // 当前j个字符能够匹配的同时后i-j个也能匹配 则前i个可以匹配 if (dp[j] && m.find(s.substr(j, i-j))!=m.end()) { dp[i] = true; break; } } } return dp[s.size()]; } }; 题型2：背包问题 题型3：打家劫舍问题 题型4：股票问题 参考链接
发表评论