免費(fèi)推廣網(wǎng)站搭建seo技術(shù)培訓(xùn)教程
暴力遞歸到動(dòng)態(tài)規(guī)劃(三)
- 最長(zhǎng)公共子序列
- 遞歸版本
- 動(dòng)態(tài)規(guī)劃
- 最長(zhǎng)回文串子序列
- 方法一
- 方法二
- 遞歸版本
- 動(dòng)態(tài)規(guī)劃
- 象棋問(wèn)題
- 遞歸版本
- 動(dòng)態(tài)規(guī)劃
- 咖啡機(jī)問(wèn)題
- 遞歸版本
- 動(dòng)態(tài)規(guī)劃
最長(zhǎng)公共子序列
這是leetcode上的一道原題 題目連接如下
最長(zhǎng)公共子序列
題目描述如下
給定兩個(gè)字符串 text1 和 text2,返回這兩個(gè)字符串的最長(zhǎng) 公共子序列 的長(zhǎng)度。如果不存在 公共子序列 ,返回 0 。
一個(gè)字符串的 子序列 是指這樣一個(gè)新的字符串:它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符(也可以不刪除任何字符)后組成的新字符串。
- 例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
兩個(gè)字符串的 公共子序列 是這兩個(gè)字符串所共同擁有的子序列。
遞歸版本
還是一樣 我們首先來(lái)設(shè)計(jì)一個(gè)函數(shù) 函數(shù)原型如下
int process(string& str1 , string& str2 , int i , int j)
這個(gè)遞歸函數(shù)的含義是 給你兩個(gè)字符串 s1 和 s2 再給你它們的一個(gè)最大下標(biāo) 現(xiàn)在要求這個(gè)函數(shù)返回它們公共子序列的最大值
參數(shù)表示如下
- int i : 表示一個(gè)字符串str1中的下標(biāo)
- int j : 表示一個(gè)字符串str2中的下標(biāo)
還是一樣 我們首先想base case
- 假如i的下標(biāo)為0 j的下標(biāo)也為0 此時(shí)我們就可以直接返回一個(gè)確定的值
代碼表示如下
// base case if (i == 0 && j == 0) { return str1[i] == str2[j] ? 1 : 0; }
此時(shí)我們排除了i 和 j都為0的情況 剩下了三種情況
- i j 其中一個(gè)為0 (兩種)
- i j都不為0
當(dāng)i j都不為0時(shí)候 我們還要討論 i j 是否為公共子序列的下標(biāo)也是分為三種情況
- i可能是 j不是
- j可能是 i不是
- i j都是
之后我們分別將代碼全部寫(xiě)好就可以了
if (i == 0){if (str1[i] == str2[j]){return 1;}else {return process(str1 , str2 , i , j-1);}}else if (j == 0){if (str1[i] == str2[j]){return 1;}else { return process(str1 , str2 , i - 1 , j); }}else {// j != 0;// i != 0;// possible i ... jint p1 = process(str1 , str2 , i - 1 , j);int p2 = process(str1 , str2 , i , j - 1);int p3 = str1[i] == str2[j] ? 1 + process(str1 , str2 , i -1 , j -1) : 0 ;return max(p1 , max (p2 , p3));}
}
動(dòng)態(tài)規(guī)劃
我們觀察原遞歸函數(shù)
process(string& str1 , string& str2 , int i , int j)
我們發(fā)現(xiàn)變化的值只有 i 和 j
于是我們可以利用i j 做出一張dp表
還是一樣 我們首先來(lái)看base case
// base case if (i == 0 && j == 0) { return str1[i] == str2[j] ? 1 : 0; }
于是我們就可以把i == 0 并且 j ==0 的這些位置值填好
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
之后根據(jù) i == 0 j ==0 這兩個(gè)分支繼續(xù)動(dòng)規(guī)
for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++){ dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j-1]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++){ dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0];}
遞歸的最后一部分依賴(lài)三個(gè)位置
else {// j != 0;// i != 0;// possible i ... jint p1 = process(str1 , str2 , i - 1 , j);int p2 = process(str1 , str2 , i , j - 1);int p3 = str1[i] == str2[j] ? 1 + process(str1 , str2 , i -1 , j -1) : 0 ;return max(p1 , max (p2 , p3));}
我們只需要再遞歸表中依次填寫(xiě)即可 代碼表示如下
int process1(string& str1, string& str2, vector<vector<int>>& dp)
{ dp[0][0] = str1[0] == str2[0] ? 1 : 0; for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++) { dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j-1]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++) { dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++) { for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++) { int p1 = dp[i-1][j]; int p2 = dp[i][j-1]; int p3 = str1[i] == str2[j] ? 1 + dp[i-1][j-1] : 0; dp[i][j] = max(p1 , max(p2 , p3)); } } return dp[str1.size() - 1][str2.size() - 1];
}
最長(zhǎng)回文串子序列
方法一
做這道題目我們其實(shí)可以復(fù)用下上面的最長(zhǎng)公共子序列的代碼來(lái)做
我們可以將字符串逆序一下創(chuàng)造出一個(gè)新的字符串
再找出這兩個(gè)字符串的最長(zhǎng)公共子序列 我們找出來(lái)的最長(zhǎng)公共子序列就是回文子序列 (其實(shí)我們可以想想兩個(gè)指針從一個(gè)字符串的兩端開(kāi)始查找)
方法二
遞歸版本
我們寫(xiě)的遞歸函數(shù)如下
int process(string& str , int L , int R)
它的含義是 我們給定一個(gè)字符串str 返回給這個(gè)字符串從L到R位置上的最大回文子串
參數(shù)含義如下
- str 我們需要知道回文子串長(zhǎng)度的字符串
- L 我們需要知道回文子串長(zhǎng)度的起始位置
- R 我們需要知道回文子串長(zhǎng)度的終止位置
所有的遞歸函數(shù)都一樣 我們首先來(lái)想base case
這道題目中變化的參數(shù)其實(shí)就只有L 和 R 所以說(shuō)我們只需要考慮L和R的base case
如果L和R相等 如果L和R只相差1
if (L == R) { return 1; } if (L == R - 1) { return str[L] == str[R] ? 2 : 1; }
之后我們來(lái)考慮下普遍的可能性
- 如果L 和 R就是回文子序列的一部分
- 如果L可能是回文子序列的一部分 R不是
- 如果L不是回文子序列的一部分 R有可能是
我們按照上面的可能性分析寫(xiě)出下面的代碼 之后返回最大值即可
int p1 = process(str , L + 1 , R); int p2 = process(str , L , R - 1);int p3 = str[L] == str[R] ? 2 + process(str , L + 1, R - 1) : 0; return max(max(p1 , p2) , p3);
動(dòng)態(tài)規(guī)劃
我們注意到原遞歸函數(shù)中 可變參數(shù)只有L 和 R 所以說(shuō)我們只需要圍繞著L 和 R建立一張二維表就可以
當(dāng)然 在一般情況下 L是一定小于等于R的 所以說(shuō)L大于R的區(qū)域我們不考慮
我們首先來(lái)看base case
if (L == R) { return 1; } if (L == R - 1) { return str[L] == str[R] ? 2 : 1; }
圍繞著這個(gè)base case 我們就可以填寫(xiě)兩個(gè)對(duì)角線的內(nèi)容
for (int L = 0; L < str.size(); L++){for(int R = L; R < str.size(); R++){if (L == R){dp[L][R] = 0;}if (L == R-1){dp[L][R-1] = str[L] == str[R] ? 2 : 1;}} }
接下來(lái)我們看一個(gè)格子普遍依賴(lài)哪些格子
int p1 = process(str , L + 1 , R); int p2 = process(str , L , R - 1);int p3 = str[L] == str[R] ? 2 + process(str , L + 1, R - 1) : 0;
從上面的代碼我們可以看到 分別依賴(lài)于
L+1 R
L , R-1
L+1 , R-1
從圖上來(lái)分析 黑色的格子依賴(lài)于三個(gè)紅色格子
于是我們就可以沿著對(duì)角線來(lái)不斷的填寫(xiě)數(shù)字
橫行一直從0開(kāi)始 縱列一直在變化 所以我們用列來(lái)遍歷
最后返回dp[0][str.size()-1]即可
int process1(string& str , vector<vector<int>>& dp){for (int L = 0; L < str.size(); L++){for(int R = 0; R < str.size(); R++){if (L == R){dp[L][R] = 1;}if (L == R-1){dp[L][R] = str[L] == str[R] ? 2 : 1;}}} for (int startR = 2; startR < str.size(); startR++){int L = 0;int R = startR;while (R < str.size()){int p1 = dp[L+1][R];int p2 = dp[L][R-1];int p3 = str[L] == str[R] ? 2 + dp[L+1][R-1] : 0;dp[L][R] = max(p1 , max(p2 , p3));L++;R++;}}return dp[0][str.size()-1];}
象棋問(wèn)題
遞歸版本
現(xiàn)在給你一個(gè)橫長(zhǎng)為10 縱長(zhǎng)為9的棋盤(pán) 給你三個(gè)參數(shù) x y z
現(xiàn)在一個(gè)馬從(0 , 0)位置開(kāi)始運(yùn)動(dòng)
提問(wèn) 有多少種方法使用K步到指定位置 (指定位置坐標(biāo)隨機(jī)給出 且一定在棋盤(pán)上)
首先我們可以想出這么一個(gè)函數(shù)
int process(int x , int y , int rest , int a , int b)
它象棋目前在 x y位置 還剩下 rest步 目的地是到 a b位置
讓你返回一個(gè)最多的路數(shù)
我們首先來(lái)想base case
- 首先肯定是剩余步數(shù)為0 我們要開(kāi)始判斷是否跳到目的地了
- 其次我們還要判斷是否越界 如果越界我們直接返回0即可
代碼表示如下
if (x < 0 || x > 9 || y < 0 || y > 8){return 0;}if (rest == 0){return (x == a && y ==b) ? 1 : 0;}
接下來(lái)我們開(kāi)始討論普遍情況 其實(shí)就是把馬的各個(gè)位置跳一遍
int ways = process(x-2 , y+1 , rest-1 , a , b); ways += process(x-1 , y+2 , rest-1 , a , b); ways += process(x+1 , y+2 , rest-1 , a , b); ways += process(x+2 , y+1 , rest-1 , a , b); ways += process(x-2 , y-1 , rest-1 , a, b); ways += process(x-1 , y-2 , rest-1 , a , b); ways += process(x+1 , y-2 , rest-1 , a, b); ways += process(x+2 , y-1 , rest-1 , a ,b);
其實(shí)這樣子我們的代碼就完成了 總體代碼如下
int process(int x , int y , int rest , int a , int b)
{if (x < 0 || x > 9 || y < 0 || y > 8){return 0;}if (rest == 0) { return (x == a && y ==b) ? 1 : 0; } int ways = process(x-2 , y+1 , rest-1 , a , b); ways += process(x-1 , y+2 , rest-1 , a , b); ways += process(x+1 , y+2 , rest-1 , a , b); ways += process(x+2 , y+1 , rest-1 , a , b); ways += process(x-2 , y-1 , rest-1 , a, b); ways += process(x-1 , y-2 , rest-1 , a , b); ways += process(x+1 , y-2 , rest-1 , a, b); ways += process(x+2 , y-1 , rest-1 , a ,b); return ways;
}
動(dòng)態(tài)規(guī)劃
我們對(duì)于原遞歸函數(shù)進(jìn)行觀察 可以得知
int process(int x , int y , int rest , int a , int b)
原函數(shù)中 變化的參數(shù)只有 x y 和rest 于是乎我們可以建立一個(gè)三維的數(shù)組
x的范圍是0 ~ 9 y的范圍是0 ~ 8 而rest的范圍則是根據(jù)我們步數(shù)來(lái)決定的 0~K
所以說(shuō)此時(shí)我們以X為橫坐標(biāo) Y為縱坐標(biāo) REST為豎坐標(biāo)
vector<vector<vector<int>>> dp(10 , vector<vector<int>>(9 , vector<int>(8 , 0)));
我們首先看base case分析下
if (x < 0 || x > 9 || y < 0 || y > 8){return 0;}
如果有越界的地方 我們直接返回0即可
if (rest == 0){return (x == a && y ==b) ? 1 : 0;}
在z軸為0的時(shí)候 我們只需要將a b 0坐標(biāo)標(biāo)記為1即可
nt process1(int k , int a , int b , vector<vector<vector<int>>>& dp)
{ dp[a][b][0] = 1; for (int z = 1; z <= k; z++) { for (int x = 0; x < 10; x++) { for (int y = 0; y < 9; y++) { int ways = pickdp(x-2 , y+1 , z-1, dp);ways += pickdp(x-1 , y+2 , z-1 , dp);ways += pickdp(x+1 , y+2 , z-1 , dp);ways += pickdp(x+2 , y+1 , z-1 , dp);ways += pickdp(x-2 , y-1 , z-1 , dp);ways += pickdp(x-1 , y-2 , z-1 , dp);ways += pickdp(x+1 , y-2 , z-1 , dp); ways += pickdp(x+2 , y-1 , z-1 , dp);dp[x][y][z] = ways;}} }return dp[0][0][k];
}
咖啡機(jī)問(wèn)題
給你一個(gè)數(shù)組arr arr[i]表示第i號(hào)咖啡機(jī)泡一杯咖啡德時(shí)間
給定一個(gè)正數(shù)N 表示第N個(gè)人等著咖啡機(jī)泡咖啡 每臺(tái)咖啡機(jī)只能輪流泡咖啡
只有一臺(tái)洗咖啡機(jī) 一次只能洗一個(gè)被子 時(shí)間耗費(fèi)a 洗完才能洗下一杯
當(dāng)然 每個(gè)咖啡杯也能自己揮發(fā)干凈 揮發(fā)干凈的時(shí)間為b 咖啡機(jī)可以并行的揮發(fā)
假設(shè)所有人拿到咖啡之后立刻喝干凈
返回從開(kāi)始等待到所有咖啡機(jī)變干凈的最短時(shí)間
我們首先來(lái)分析下題目
這里其實(shí)是兩個(gè)問(wèn)題
- 問(wèn)題一 每個(gè)人喝咖啡喝完的時(shí)間是多少
- 問(wèn)題二 每個(gè)人洗完的時(shí)間是多少
對(duì)于問(wèn)題一 我們可以使用一個(gè)小根堆來(lái)做
我們定義一個(gè)機(jī)器類(lèi) 里面有兩個(gè)成員函數(shù)
機(jī)器的開(kāi)始時(shí)間和機(jī)器的使用時(shí)間 我們使用它們相加之和來(lái)作為小根堆排序的依據(jù)
之后我們就能得到每個(gè)人喝完咖啡的最優(yōu)解了
class Machine
{ public: int _starttime; int _worktime; public: int getsum() const { return _starttime + _worktime; } public: Machine() = default; Machine(int st , int wt) :_starttime(st) ,_worktime(wt) {} bool operator()(const Machine& obj1 , const Machine& obj2) { return obj1.getsum() > obj2.getsum(); }
};
vector<int> process(vector<int>& arr , int num)
{vector<int> ans;priority_queue<Machine , vector<Machine> , Machine> heap;for (auto x : arr) {heap.push(Machine(0 , x));}for (int i = 0; i < num; i++){Machine cur = heap.top();heap.pop();ans.push_back(cur.getsum());cur._starttime += cur._worktime;heap.push(Machine(cur._starttime , cur._worktime));}return ans;
}
遞歸版本
我們?cè)趯?xiě)遞歸版本的時(shí)候首先要想到遞歸函數(shù)的含義
它的含義是返回一個(gè)所有咖啡杯都被洗完的最小值
之后我們可以想base case 當(dāng)什么樣的時(shí)候 該函數(shù)無(wú)法遞歸了
最后列出所有可能性即可
int process(vector<int>& end , int index , int a , int b , int avltime)
{if (index == static_cast<int>(end.size())){return 0;} // possible 1 int p1 = max(a + end[index] , process(end , index+1 , a , b , avltime)); // possible 2 int p2 = max(b + end[index], process(end , index+1 , a , b , avltime + b)); return min(p1 , p2);
}
動(dòng)態(tài)規(guī)劃
這個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃涉及到一個(gè)大小問(wèn)題
因?yàn)槲覀儫o(wú)法確定avltime使用到的時(shí)間 所以這里有兩種解決方案
- 將它開(kāi)辟的足夠大
- 根據(jù)最大值計(jì)算 (假設(shè)所有人都用咖啡機(jī)洗)
int dpprocess(vector<int>& end , int a , int b , vector<vector<int>> dp)
{// dp[N][...] = 0;for (int indexdp = static_cast<int>(end.size()) - 1; indexdp >= 0 ; indexdp--){for (int freetime = 0; freetime <= 10000 ; freetime++){int p1 = max(a + end[indexdp] , dp[indexdp+1][freetime]);int p2 = max(b + end[indexdp] , dp[indexdp+1][freetime+b]);dp[indexdp][freetime] = min(p1 , p2);}}return dp[0][0];
}