前言
動態(tài)規(guī)劃是筆試中經(jīng)常出現(xiàn)的一類題目瓢湃。掌握他很關(guān)鍵。
網(wǎng)易題目
小Q和牛博士合唱一首歌曲,這首歌曲由n個音調(diào)組成,每個音調(diào)由一個正整數(shù)表示业簿。
對于每個音調(diào)要么由小Q演唱要么由牛博士演唱,對于一系列音調(diào)演唱的難度等于所有相鄰音調(diào)變化幅度之和, 例如一個音調(diào)序列是8, 8, 13, 12, 那么它的難度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示絕對值)。
現(xiàn)在要對把這n個音調(diào)分配給小Q或牛博士,讓他們演唱的難度之和最小,請你算算最小的難度和是多少。
如樣例所示: 小Q選擇演唱{5, 6}難度為1, 牛博士選擇演唱{1, 2, 1}難度為2,難度之和為3,這一個是最小難度和的方案了撼唾。
貪心解法（錯誤）
將所有數(shù)字進行排序，取最大的兩個數(shù)字差作為間隔哥蔚，取其中一下半作為小Q的音符倒谷，取另一上半作為牛博士的音符，然后計算結(jié)果肺素。最終能過通過60%的用例恨锚。
如果時間不夠，或者不會的情況可以使用這種解法倍靡。
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> nums;
for(int i=0;i<n;i++)
{
int num;
cin >> num;
nums.push_back(num);
}
vector<int> nums_sort(nums.begin(), nums.end());
sort(nums_sort.begin(), nums_sort.end());
int max_gap = 0;
auto max_gap_it = nums_sort.begin();
for(auto it=nums_sort.begin(); it!=nums_sort.end()-1; it++){
if(*(it+1) - *it > max_gap){
max_gap = *(it+1) - *it;
max_gap_it = it;
}
}
int max_gap_num = *max_gap_it;
int ret = 0;
int last_1 = -1;
int last_2 = -1;
for(auto it = nums.begin(); it!=nums.end(); it++){
if(*it <= max_gap_num){
if(last_1 != -1){
ret += abs(*it - last_1);
}
last_1 = *it;
}
else{
if(last_2 != -1){
ret += abs(*it - last_2);
}
last_2 = *it;
}
}
cout << ret;
}
動態(tài)規(guī)劃小思
由于我對動態(tài)規(guī)劃一點也不了解猴伶，先從找零開始。
- 找零問題
動態(tài)規(guī)劃的核心在于問題的分解和子問題遞歸組合變成原問題塌西。
舉個例子他挎，假設我們有面值為1元、3元和5元的硬幣若干枚捡需，如何用最少的硬幣湊夠11元办桨？
如果你是個人類的話，你會說站辉，我大眼一瞪呢撞，兩個五元和一個一元损姜，總共3個硬幣。我們換個例子殊霞，假設題目是237元呢摧阅？你可能會說，我先用5塊錢換出200元绷蹲，然后找到剩下37元的最優(yōu)組合棒卷。這種方法實際上是默認了將237元分成了兩份，并假設兩份的組合是最優(yōu)組合祝钢。如果真是這樣的話比规，那么就沒什么問題了±褂ⅲ可問題就出在分的200和37元蜒什，沒有方法能證明這是有效的分割，所以動態(tài)規(guī)劃就是建立在有效分割上的龄章。
分治算法與動態(tài)規(guī)劃也是建立在分割上的吃谣。只是動態(tài)規(guī)劃涉及到狀態(tài)轉(zhuǎn)移，而分治算法沒有狀態(tài)轉(zhuǎn)移做裙。分治算法可以由上向下分解岗憋，而動態(tài)規(guī)劃通常由下向上構(gòu)建。
動態(tài)規(guī)劃會涉及到兩個維度锚贱，第一個維度通常和問題的規(guī)模相關(guān)仔戈，第二個維度需要從題目中提取出來。在本題目中拧廊，第二個維度是允許使用的硬幣监徘，例如，允許使用1元吧碾、允許使用1元和3元凰盔、允許使用1元3元5元。我們把他記為下標1,2,3倦春，我們用j來代表這個變量户敬，如果用i來表示當前題目的規(guī)模，也就是237睁本，那么我們要求的是c[i][j] 為 c[237][3]的值尿庐。對于這個問題，我們可以分兩種假設呢堰，第一種假設抄瑟，這個最優(yōu)解中5元的數(shù)量>0，第二種假設枉疼，這個最優(yōu)值中5元的數(shù)量=0.對于第一種假設c[237][3]=c[237][2]皮假，因為沒有使用5元鞋拟，那么就不需要5元了，這個最優(yōu)解的解應該和只是用1元和3元的情況一致惹资。對于第二種情況严卖，由于這個解中必然有一個5元（因為你假設他大于0），那么布轿，除了這枚5元錢，剩下的錢數(shù)是232元錢来颤。由于原來c[237][3]是135元找237元的最優(yōu)值汰扭，又因為其中必然有一枚5元，在最優(yōu)值狀態(tài)下拿掉其中必然存在的一枚硬幣福铅，剩下的錢所組成的錢數(shù)必然也是最優(yōu)狀態(tài)萝毛，(假設子問題不是最優(yōu)的，即237元找135元的硬幣數(shù)中構(gòu)成232元的解有更優(yōu)解滑黔，則237找135元也有更有解笆包，和c[237][3]為最優(yōu)解矛盾)，那么c[232][3]的值就是c[237][3]-1的值略荡。
這樣我們可以推導出
c[i][j] = c[i][j-1] 假設1
c[i][j] = c[i-j下標代表的錢數(shù)][j]+1 假設2
如果寫成min的形式庵佣，就是熟知的狀態(tài)轉(zhuǎn)移方程了。
最終求的是c[11][5]汛兜，使用表格從c[0][0]狀態(tài)開始向右下角推巴粪，最終可以推出答案。
我們要記住
題目的最優(yōu)解不一定是狀態(tài)矩陣的右下角的值
我們必須時刻記住粥谬，狀態(tài)矩陣的右下角方格不一定就是直接的最優(yōu)解肛根。如果這樣想的話，往往會陷入困境漏策。為此派哲，我們只能這樣設想，矩陣i掺喻，j一定和題目中的兩個維度有關(guān)芭届，但是dp[i][j]不一定代表了最優(yōu)解的值。
例如本題目巢寡，題目要求求出最優(yōu)難度系數(shù)喉脖。假如dp[i_max][j_max]就是最優(yōu)難度系數(shù)，那i和j是什么的下標呢抑月？树叽？是無解的。反過來想谦絮，最優(yōu)難度系數(shù)到底是什么呢题诵？我們想想看洁仗，因為存在狀態(tài)轉(zhuǎn)移，最優(yōu)狀態(tài)必然是從多個狀態(tài)中獲取到的最小值性锭。i代表什么呢赠潦？i如果代表當前唱的音符，那么j代表什么呢草冈？j就只能代表另外一個人唱的音符了她奥。那么最優(yōu)狀態(tài)下，一共會有多少種情況怎棱，就從這些情況來推算最優(yōu)的值是哪個哩俭。在最優(yōu)狀態(tài)下，必然有一個人在唱最后一個音符拳恋，那么另一個人可能一個都沒有唱凡资，可能在唱第一個音符，可能在唱第二個音符谬运。隙赁。“鹋可能在唱倒數(shù)第二個音符伞访。然后我們計算所有情況的最小值，就知道了問題的最優(yōu)解式廷。
還有一個問題咐扭，i和j是不是要分人？如果i代表小Q唱的滑废，j代表牛博士唱的蝗肪，那么這個矩陣就是對稱的，我們多計算了一半的內(nèi)容蠕趁。其實我們不關(guān)心到底是誰唱的薛闪，因為都一樣。我們只能這樣想俺陋，其中一個i是當前人唱的豁延，j是上一個人唱到哪里了。
c[i][j]可能由哪些狀態(tài)轉(zhuǎn)移過來呢腊状？
例如某人唱到了第6個音符诱咏，另一個人最后一次唱到了第3個音符，此時如果當前的總的難度是最小的缴挖，那么有以下結(jié)論：
第6個音符袋狞、第5、第4個音符都是第一個人唱的。因為第二個人才唱到了第三個音符苟鸯，他不可能去唱后面的音符同蜻。
所以c[6][3] = c[5][3] + 56難度差 = c[4][3] + 45難度差。
但是c[4][3]是怎么轉(zhuǎn)移來的呢早处？如果此時第一個人唱到了第4個音符湾蔓，另一個人唱到了第3個音符，這說明第一個人唱第4個音符中斷了第二個人唱的音符砌梆。由于不知道上一次第一個人是從哪里跳到第4個音符的默责，所以我們分別假設是從可能的所有音符跳過來的，如果是從第二個音符跳過來的咸包，那么就是c[3][2]+ 34差傻丝。如果是從第一個音符跳過來的，那么就是c[3][1]+14差诉儒。如果是從沒有跳過來的，那么就是c[3][0]+04差亏掀。由于第一個人唱的時候忱反，第二個人上一次唱的總是比第一個人唱的要小，所以我們不需要考慮j>=i的時候滤愕。
基于此温算，有以下代碼
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <array>
using namespace std;
vector<int> nums;
array<array<int, 2100>, 2100> dp;
/* 計算兩個音符之間的難度。注意第一個音符的下標在輸入數(shù)據(jù)里面是0间影，有個差1的關(guān)系注竿。如果起始音符是0，說明第一次唱魂贬，不增加難度 */
int diffcult(int s, int e)
{
if(s == 0) return 0;
// printf("diffcult %d %d to %d %d is %d \n", s,nums[s-1], e,nums[e-1], abs(nums[e-1] - nums[s-1]));
return abs(nums[e-1] - nums[s-1]);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
nums.push_back(num);
}
/* 從0開始向后考慮巩割，直到考慮完所有音符，第一個人最差的情況是沒有唱付燥，此時j也沒有唱宣谈，直接continue了 */
for (int i = 0; i <= n; i++)
{
/* 這里也是從0開始考慮，因為第一個人最差一個都不唱键科，就是處于0 */
for (int j = 0; j <= n; j++)
{
/* 不考慮后面的情況闻丑。當然也可以直接寫到上面的范圍限制里面 */
if (j >= i)
continue;
/* 如果是一般情況下，比如第一個人在唱6音符時勋颖，第二個人在唱3音符嗦嗡，顯然是從dp[5][3]轉(zhuǎn)移來的 */
if (j + 1 < i)
{
dp[i][j] = dp[i - 1][j] + diffcult(i - 1, i);
}
/* 否則，如果第二個人剛唱完就被第一個人搶唱了饭玲，那么第一個人唱的音符就可能是前面跳過來的 */
if (j + 1 == i)
{
/* k表示i是從第幾個跳過來的 */
int min_cost = -1;
for (int k = 0; k < j; k++)
{
int cost = dp[j][k] + diffcult(k, j + 1);
/* 只用記錄最小跳唱難度 */
if(min_cost == -1 || min_cost > cost){
min_cost = cost;
}
}
if(min_cost == -1) min_cost = 0;
dp[i][j] = min_cost;
}
// for(int a=0;a<=n;a++){
// for(int b=0;b<=n;b++){
// if(a==i && b == j){
// printf("\t【%d】", dp[a][b]);
// }
// else printf("\t%d", dp[a][b]);
// }
// // printf("\n");
// }
// printf("\n");
}
}
int min_cost = -1;
for(int j=0;j<n;j++){
if(min_cost == -1 || min_cost > dp[n][j]){
min_cost = dp[n][j];
}
}
printf("%d", min_cost);
}
其實已經(jīng)明白了為什么動態(tài)規(guī)劃會以這種方式進行呈現(xiàn)了侥祭。二維動態(tài)規(guī)劃問題的最關(guān)鍵的點在于：
線性增長問題的平面展開
例如找零問題，展開第二個維度就是以當前硬幣種類找零。而合唱問題卑硫，則是以唱到當前位置時且上一個唱到某個位置時的難度最小值徒恋。最長回文子串，則變得是起始位置欢伏。
最長回文子串的i表示從第i個字符開始入挣，第j個字符結(jié)束時的最長子串問題。當i是起始字符硝拧，j是終止字符径筏，則是問題的答案。
對于最小的子問題來說障陶，就是單個字符了滋恬，他的長度就是1，對于長字符串來說抱究，如果他兩邊的字符不一樣恢氯，那么等于去掉右邊或者左邊的字符中小的那一個。如果兩邊的字符一樣鼓寺，那么就等于去掉兩邊的子串的值加2勋拟。
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp;
dp.resize(s.size() + 1);
for (int i = 0; i < s.size() + 1; i++)
{
dp[i].resize(s.size() + 1);
}
int len = s.size();
for(int t=0;t<len;t++){
for(int j=t; j<len;j++){
int i = j-t;
if(i==j){
dp[i][j] = 1;
}
else if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1] + 2;
}
else{
if(dp[i+1][j]> dp[i][j-1]){
dp[i][j] = dp[i+1][j];
}
else{
dp[i][j] = dp[i][j-1];
}
}
}
}
return dp[0][len-1];
}
};
- 最大子串問題
這個題目也很經(jīng)典，按照上一個題目的思路妈候，我們依次求出所有串的長度敢靡，就得到了最大的子串。
然而事情不是這么簡單苦银，這個題目可以用一維來做啸胧。（注意其中有負數(shù)）。
我們的記得幔虏，最后一個方格內(nèi)存的不一定就是最優(yōu)解纺念。往往我們會認為dp[i]就是從開始到這個位置中，能夠找到的最大的子串的值想括。但是這個最大的子串與i又沒有什么關(guān)系柠辞，似乎i往左一位和往右移一位沒有什么區(qū)別。如果我們的下標與題目中的最優(yōu)解產(chǎn)生了“松弛”的關(guān)系主胧，我們一定要警惕起來叭首。我們需要緊緊把下標和最優(yōu)解綁在一起。最優(yōu)解必然和i產(chǎn)生直接關(guān)系踪栋。那么i是最優(yōu)的什么焙格。你會想到，i就是必須以第i個數(shù)字為結(jié)尾的串的最大值夷都。最大子串就是遍歷dp矩陣眷唉，找到那個最大的值。
狀態(tài)方程也容易寫出來了，每當我們多考慮一個數(shù)字冬阳，以這個數(shù)字為結(jié)尾的子串的最大值有兩種情況蛤虐，第一種就是以上一個數(shù)字為結(jié)尾的最大子串加上這個數(shù)字，第二種情況就是不以上一個數(shù)字 為結(jié)尾肝陪。顯然第二種情況就是以這個數(shù)字為開頭的情況驳庭，并且只有這一個數(shù)字。
input表示輸入矩陣氯窍，dp表示狀態(tài)矩陣
我們有 dp[i] = max (dp[i-1] + input[i] , input[i])
