朝花夕拾——动态规划
2020-07-17 17:00:43阅读量: 10
· · · 正文 · · ·
- Overview
- 最长连续子序列和
- LeetCode 300. 最长递增子序列 LIS - 方法1:朴素动态规划 - 方法2:二分+动态规划
- 非连续最大子集
- LeetCode 1143. 最长公共子序列 LCS
- hdu1506 Largest Rectangle in a Histogram
- LeetCode 338. Counting Bits
- 能不能组成S?
- web数据挖掘中的编辑距离
- 稍微变了一小下的01背包
- 96. 不同的二叉搜索树
- 354. 俄罗斯套娃信封问题
Overview
最长连续子序列和
-2 6 -1 5 4 -7 2 3
求连续的子数列最大和。
根据递归的思路想:f(n) = max{ f(n-1) + num[n], num[n] }
LeetCode 300. 最长递增子序列 LIS
题目链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。(子序列可以不连续)
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
输入:nums = [7,7,7,7,7,7,7]
输出:1
终于碰到这个题了,之前一直分不清LCS和LIS。
方法1:朴素动态规划
用一个二重循环来实现,时间复杂度n方。
定义dp[i]
的含义,以nums[i]
结尾的子序列的最大长度。
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
方法2:二分+动态规划
考虑方法一中的内层循环,是否可以优化。
重新定义dp[i]
,长度为i
的子序列中最后一位数字的最小值。
做法:维护一个单调数组dp[]
,在遍历nums[]
的时候,如果当前元素a
比dp
的栈顶元素大,则直接推入栈,如果比栈顶元素小,则二分这个数组,找到最小的比a
大的数dp[k]
,替换它,以保证在长度k
下,dp[k]中的值始终最小。
dp
的长度就是最终结果。
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(1, nums[0]);
for (int i=1; i<nums.size(); ++i) {
if (nums[i] > dp[dp.size() - 1]) {
dp.push_back(nums[i]);
continue;
}
int lo = 0;
int hi = dp.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[i] > dp[mid]) {
lo = mid + 1;
} else {
hi = mid;
}
}
dp[lo] = nums[i];
}
return dp.size();
}
非连续最大子集
给你一个序列arr = {}
请你求出它的一个子集,要求,子集和最大,且子集的元素在原序列终不能相邻
入门DP
对于每一个数,dp[i] = max{ dp[i-1], dp[i] + arr[i-1] }
那么就和斐波那契有点像了
LeetCode 1143. 最长公共子序列 LCS
给定两个字符串 text1
和 text2
,返回这两个字符串的最长 公共子序列
的长度。如果不存在 公共子序列
,返回 0
。
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。
创建二维数组dp
,其中dp[i][j]
表示text[0:i]
和text2[0:j]
的最长公共子序列的长度。
int longestCommonSubsequence(string text1, string text2) {
int dp[1003][1003], n = text1.size(), m = text2.size();
memset(dp, 0, sizeof(dp));
dp[0][0] = text1[0] == text2[0] ? 1 : 0;
for (int i=1; i<m; ++i) {
dp[0][i] = text1[0] == text2[i] ? 1 : max(dp[0][i-1], 0);
}
for (int i=1; i<n; ++i) {
dp[i][0] = text1[i] == text2[0] ? 1 : max(dp[i-1][0], 0);
}
for (int i=1; i<n; ++i) {
for (int j=1; j<m; ++j) {
dp[i][j] = text1[i] == text2[j] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n-1][m-1];
}
hdu1506 Largest Rectangle in a Histogram
对于每一个高度h[i]
,搜索它能到达的最左,和最右,最大面积Smax = Max{ i | 面积Si = (最右 - 最左 + 1) *h[i] }
这样的时间复杂度为O(n^2),必超时
举例 2,3,4,5
要判断2能到达最右的位置,不需要循环比较,只需要知道3能到达的最右是哪里,因为若3能到达的位置,2必然也能到达
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4
5 int main()
6 {
7 int n;
8 while(scanf("%d", &n) && n)
9 {
10 long long h[100007];
11 long long l[100007];
12 long long r[100007];
13 for(int i=1;i<=n;i++)
14 {
15 scanf("%lld", &h[i]);
16 l[i] = r[i] = i;
17 }
18 h[0] = h[n+1] = -1;
19 for(int i=1;i<=n;i++)
20 {
21 while(h[i] <= h[l[i]-1]) {
22 l[i] = l[l[i]-1];
23 }
24 }
25 for(int i=n;i>=1;i--)
26 {
27 while(h[i] <= h[r[i]+1]) {
28 r[i] = r[r[i]+1];
29 }
30 }
31 long long ans = 0;
32 for(int i=1;i<=n;i++)
33 {
34 ans = ans > (r[i]-l[i]+1)*h[i] ? ans : (r[i]-l[i]+1)*h[i];
35 }
36 printf("%lld\n",ans);
37 }
38 }
LeetCode 338. Counting Bits
第一道自己做出来的DP!!!纪念合影,你没听错我就是这么菜
给你一个非负整数num,求从0到num的num+1个数中,每个数二进制表示的1的个数,返回一个数组
就是dp嘛,暴力的办法就是for from 0 to num,每个数的每一个二进制位比较,设二进制位最坏长度为31位,那么复杂度就是O(31*n)
其中大量重复计算,所以用动态规划解决,自底向上
1 class Solution {
2 public:
3 vector<int> countBits(int num) {
4 vector<int>dp(num+1);
5 dp.resize(num+1);
6 dp[0] = 0;
7 for(int i=1;i<=num;i++)
8 {
9 if((i & 1) == 0)
10 dp[i] = dp[i>>1];
11 else
12 dp[i] = dp[i>>1] + 1;
13 }
14 return dp;
15 }
16 };
能不能组成S?
给你一个序列arr = {}
,和一个数S,问你序列里的数能不能组成S,又是简单的选和不选问题
web数据挖掘中的编辑距离
这个有点难想
稍微变了一小下的01背包
uim拉着基友小A到了一家……餐馆,很低端的那种。uim指着墙上的价目表说:“随便点”。
题目描述 不过uim由于买了一些书,口袋里只剩M元(M≤10000)。
餐馆虽低端,但是菜品种类不少,有N种(N≤100),第i种卖a元(ai≤1000)。由于是很低端的餐馆,所以每种菜只有一份。
小A奉行“不把钱吃光不罢休”,所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。
思路:和裸的价值+容量的01背包不同,原来是求可放入背包且价值最大化,这个是必须装满背包,求有多少种方案。
根据题意设数组dp[i][j]为前i种菜品恰好花费j元的点菜方法数。那么,考虑第i种菜点或不点,若不点,则说明前i-1种菜,已经恰好花费j元;若点,则说明前i-1种菜,花费j-ai元,这样,在点完第i种菜后,恰好花费j元。
因此容易得出公式
dp[i][j] = dp[i-1][j] + dp[i-1][j-ai]
然而很多人想到这里以后就不知道接下来怎么做了。(比如说我)
但是在看到"j - ai"后,应该能想到,对j - ai的情况进行枚举。
- 若
j > ai
,则和上式一样。 - 若
j < ai
,则说明第i道菜,压根就买不起,因此dp[i][j] = dp[i-1][j]
。 - 若
j == ai
,那么说明可以只点这一道菜作为一种新的方案,dp[i][j] = dp[i-1][j] + 1
。
96. 不同的二叉搜索树
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/unique-binary-search-trees/ 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这个题我一开始没有想到能拿dp做。
class Solution {
public:
int numTrees(int n) {
int g[20] = {1, 1};
for (int i = 2; i <= n; ++ i) {
for (int j = 1; j <= i; ++ j) {
g[i] += g[j-1] * g[i-j];
}
}
return g[n];
}
};
354. 俄罗斯套娃信封问题
题目链接:https://leetcode-cn.com/problems/russian-doll-envelopes/
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式(w, h)
出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
说明: 不允许旋转信封。
是不是很像LIS的变型?但是这里要注意对原数组进行一个从小到大的排序。对于w从小到大排序,对于h从大到小排序,我这里还没有想明白,为什么h降序排序就是对的,升序排序就是错的。
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](const vector<int> &u, const vector<int> &v){
return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
});
vector<pair<int, int>> dp(1, {envelopes[0][0], envelopes[0][1]});
for (const auto &envelope : envelopes) {
if (envelope[0] > dp[dp.size() - 1].first && envelope[1] > dp[dp.size() - 1].second) {
dp.push_back({envelope[0], envelope[1]});
continue;
}
int lo = 0;
int hi = dp.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (envelope[0] > dp[mid].first && envelope[1] > dp[mid].second) {
lo = mid + 1;
} else {
hi = mid;
}
}
dp[lo] = {envelope[0], envelope[1]};
}
return dp.size();
}
我的代码还是比较复杂了,看了题解以后发现,只需要对h做LIS即可,因为h是降序排列的,当你对h做LIS时,别忘了,LIS是最长递增子序列,只要被你选入的h一定是递增的,但是你又是降序排列的,这说明你选取的两个信封一定有w2 > w1
,这里是严格大于,仔细想一想。