朝花夕拾——动态规划
Overview
最長連續(xù)子序列和
-2 6 -1 5 4 -7 2 3求連續(xù)的子數(shù)列最大和。
根據(jù)遞歸的思路想：f(n) = max{ f(n-1) + num[n], num[n] }
LeetCode 300. 最長遞增子序列 LIS
題目鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。（子序列可以不連續(xù)）
輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。輸入：nums = [7,7,7,7,7,7,7] 輸出：1終于碰到這個(gè)題了，之前一直分不清LCS和LIS。
方法1：樸素動(dòng)態(tài)規(guī)劃
用一個(gè)二重循環(huán)來實(shí)現(xiàn)，時(shí)間復(fù)雜度n方。
定義dp[i]的含義，以nums[i]結(jié)尾的子序列的最大長度。
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：二分+動(dòng)態(tài)規(guī)劃
考慮方法一中的內(nèi)層循環(huán)，是否可以優(yōu)化。
重新定義dp[i]，長度為i的子序列中最后一位數(shù)字的最小值。
做法：維護(hù)一個(gè)單調(diào)數(shù)組dp[]，在遍歷nums[]的時(shí)候，如果當(dāng)前元素a比dp的棧頂元素大，則直接推入棧，如果比棧頂元素小，則二分這個(gè)數(shù)組，找到最小的比a大的數(shù)dp[k]，替換它，以保證在長度k下，dp[k]中的值始終最小。
dp的長度就是最終結(jié)果。
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();}非連續(xù)最大子集
給你一個(gè)序列arr = {}
請(qǐng)你求出它的一個(gè)子集，要求，子集和最大，且子集的元素在原序列終不能相鄰
入門DP
對(duì)于每一個(gè)數(shù)，dp[i] = max{ dp[i-1], dp[i] + arr[i-1] }
那么就和斐波那契有點(diǎn)像了
LeetCode 1143. 最長公共子序列 LCS
給定兩個(gè)字符串 text1 和 text2，返回這兩個(gè)字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。
輸入：text1 = "abcde", text2 = "ace" 輸出：3 解釋：最長公共子序列是 "ace" ，它的長度為 3 。創(chuàng)建二維數(shù)組dp，其中dp[i][j] 表示text[0:i]和text2[0:j]的最長公共子序列的長度。
hdu1506 Largest Rectangle in a Histogram
對(duì)于每一個(gè)高度h[i]，搜索它能到達(dá)的最左，和最右，最大面積Smax = Max{ i | 面積Si = (最右 - 最左 + 1) *h[i] }
這樣的時(shí)間復(fù)雜度為O（n^2）,必超時(shí)
舉例 2,3,4,5
要判斷2能到達(dá)最右的位置，不需要循環(huán)比較，只需要知道3能到達(dá)的最右是哪里，因?yàn)槿?能到達(dá)的位置，2必然也能到達(dá)
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！！！紀(jì)念合影，你沒聽錯(cuò)我就是這么菜
給你一個(gè)非負(fù)整數(shù)num，求從0到num的num+1個(gè)數(shù)中，每個(gè)數(shù)二進(jìn)制表示的1的個(gè)數(shù)，返回一個(gè)數(shù)組
就是dp嘛，暴力的辦法就是for from 0 to num，每個(gè)數(shù)的每一個(gè)二進(jìn)制位比較，設(shè)二進(jìn)制位最壞長度為31位，那么復(fù)雜度就是O（31*n）
其中大量重復(fù)計(jì)算，所以用動(dòng)態(tài)規(guī)劃解決，自底向上
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？
給你一個(gè)序列arr = {}，和一個(gè)數(shù)S，問你序列里的數(shù)能不能組成S，又是簡(jiǎn)單的選和不選問題
web數(shù)據(jù)挖掘中的編輯距離
這個(gè)有點(diǎn)難想
稍微變了一小下的01背包
uim拉著基友小A到了一家……餐館，很低端的那種。uim指著墻上的價(jià)目表說：“隨便點(diǎn)”。
題目描述
不過uim由于買了一些書，口袋里只剩M元(M≤10000)。
餐館雖低端，但是菜品種類不少，有N種(N≤100)，第i種賣a?元(ai?≤1000)。由于是很低端的餐館，所以每種菜只有一份。
小A奉行“不把錢吃光不罷休”，所以他點(diǎn)單一定剛好吧uim身上所有錢花完。他想知道有多少種點(diǎn)菜方法。
思路：和裸的價(jià)值+容量的01背包不同，原來是求可放入背包且價(jià)值最大化，這個(gè)是必須裝滿背包，求有多少種方案。
根據(jù)題意設(shè)數(shù)組dp[i][j]為前i種菜品恰好花費(fèi)j元的點(diǎn)菜方法數(shù)。那么，考慮第i種菜點(diǎn)或不點(diǎn)，若不點(diǎn)，則說明前i-1種菜，已經(jīng)恰好花費(fèi)j元；若點(diǎn)，則說明前i-1種菜，花費(fèi)j-ai元，這樣，在點(diǎn)完第i種菜后，恰好花費(fèi)j元。
因此容易得出公式
dp[i][j] = dp[i-1][j] + dp[i-1][j-ai]然而很多人想到這里以后就不知道接下來怎么做了。（比如說我）
但是在看到"j - ai"后，應(yīng)該能想到，對(duì)j - ai的情況進(jìn)行枚舉。
- 若j > ai，則和上式一樣。
- 若j < ai，則說明第i道菜，壓根就買不起，因此dp[i][j] = dp[i-1][j]。
- 若j == ai，那么說明可以只點(diǎn)這一道菜作為一種新的方案，dp[i][j] = dp[i-1][j] + 1。
96. 不同的二叉搜索樹
給定一個(gè)整數(shù) n，求以 1 … n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-binary-search-trees/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
這個(gè)題我一開始沒有想到能拿dp做。
354. 俄羅斯套娃信封問題
題目鏈接：https://leetcode-cn.com/problems/russian-doll-envelopes/
給定一些標(biāo)記了寬度和高度的信封，寬度和高度以整數(shù)對(duì)形式(w, h)出現(xiàn)。當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。
請(qǐng)計(jì)算最多能有多少個(gè)信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
說明:
不允許旋轉(zhuǎn)信封。
是不是很像LIS的變型？但是這里要注意對(duì)原數(shù)組進(jìn)行一個(gè)從小到大的排序。對(duì)于w從小到大排序，對(duì)于h從大到小排序，我這里還沒有想明白，為什么h降序排序就是對(duì)的，升序排序就是錯(cuò)的。
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(); }我的代碼還是比較復(fù)雜了，看了題解以后發(fā)現(xiàn)，只需要對(duì)h做LIS即可，因?yàn)閔是降序排列的，當(dāng)你對(duì)h做LIS時(shí)，別忘了，LIS是最長遞增子序列，只要被你選入的h一定是遞增的，但是你又是降序排列的，這說明你選取的兩個(gè)信封一定有w2 > w1，這里是嚴(yán)格大于，仔細(xì)想一想。
總結(jié)
以上是生活随笔為你收集整理的朝花夕拾——动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： OpenCV实践（4）- 叠加两幅图片
- 下一篇： 容灾恢复 | 记一次K8S集群中etcd