---------------------做過的DP題目都做不出來，老廢物了------------------
DP學的很亂，對于DP的概念理解應該不會有偏差，并且對于DP的解題步驟也總結了一套方法，但是自己拿到一個DP題目卻仍然無法不借助題解把它獨立做出來，于是便要鎮靜的去接受現實：
自己dp依舊很爛，總結幾點原因，
1.自己做dp題目時，雖然也思考了很久，但最侄訓是過多的依靠題解，有利有弊，
好處在于一個題目我知道用什么樣的方法去解決會更方便，會有很多想法；
壞處在于做DP題目時沒有經歷過一個系統的思考獨立做出來，缺少完整的解題程序，必然會遺漏一些細節處理，最重要的一點，缺乏底氣和信心，而底氣和信心源于一道道題目和一次次成功，
2.DP的程序是一個實際上就是狀態轉移，我每次寫出的狀態轉移方程都是從中間一個狀態著手，而對于整個dp程序其實并不熟悉，解決方法也好辦---->>>花心思不斷的模擬和制圖，清楚了解每一個轉移程序，畫上幾十張差不多能找到門道，
總結所有見過的經典DP題目，簡單的不嫌麻煩，難的更不要放棄，重新來過，重頭新學DP，沖沖沖！！！
A - Jumping Cows
注意點：
1.給出跳高藥水的順序不變，但可以跳過某瓶藥水，
2.奇數時間服用藥水增加跳高能力，偶數時間減少，
3.牛剛開始的跳高能力為0.
解題:
1.確定dp陣列含義---->>>奇數時間，偶數時間，可用dp[0][i]表示偶數時間在第i瓶藥時最大跳高能力；dp[1][i]表示偶數時間在第i瓶藥時最大跳高能力，
2.找出狀態轉移方程，
3.定義初始狀態，由注意點可知，牛初始跳高能力為0，定義dp[0][0]為0，
B - 反恐訓練營
注意點：
1.為了得到更多分數，要子彈型別和恐怖分子型別一致，不難看出是個公共子序列問題
（如果Z既是X的子序列，又是Y的子序列，則稱Z為X和Y的公共子序列：此外子序列不必連續，區別與欄位和），
2.輸入那一欄中，第一個數字表示子彈和恐怖分子的型別數，并不表示子彈序列長度和恐怖分子序列長度，
3.若從字串從0開始存，為了使dp[i-1][j-1]不會小于0，for回圈從1開始，反正就注意下標；若覺得難處理，換用字符陣列從1開始存，肯定不會出問題，
解題：
1.確定dp陣列含義---->>>確定要定義一個二維陣列dp[i][j]，其中i表示序列X的第i位字母，j表示序列Y的第j位字母，dp[i][j]表示搜索到X第i位，Y第j位時最長公共子序列，
2.找出狀態轉移方程，
3.找出初始狀態，dp[0][0]定義為0，用string，注意將字符從1開始存，（我傾向從1開始存，但要用c語言中的輸入輸出，加強學習），否則用字符陣列，邏輯清晰一點，
char s2[2100],s3[2100];
cin>>s2+1; //從1開始存
cin>>s3+1;
int len2=strlen(s2+1); //從字符1后開始計算長度
int len3=strlen(s3+1);
C - FatMouse’s Speed
注意點：
1.體重嚴格遞增，速度嚴格遞減，也就是對體重排序后對于速度找最長下降子序列，
2.本題難在對于老鼠編號的處理上，采用vector容器好一點，但要區分老鼠的編號并不是子序列的長度，
解題：
1.確定dp陣列含義---->>>開始認為要開二維陣列，代碼寫到一半，發現有問題，直接dp[i]表示到第i個老鼠時的子序列長度，
2.找出狀態轉移方程，
3.找出初始狀態，每只老鼠本身代表的長度即為1，因此dp[i]初始都為1.
D - Tickets （再看發現好簡單）
1.確定dp陣列含義---->>>第i個人時的最小花費時間，
2.狀態轉移方程---->>>第i個人時花費的最小時間
3.初始狀態，0個人最小時間自然為0，1個人時時間為當前那人時間，
E - Employment Planning
1.確定dp陣列含義---->>>題目中涉及到月份，雇傭人數，最小花費，不難想到為第i個月雇傭j個人所需要的最小花費，
2.找出狀態轉移方程---->>>每個月雇傭人數最少是a[i],由于hire，salary，hire的費用關系，導致具體雇傭多少人不確定，但上限是月份中雇傭最多人數；要先確定上一個月雇傭人數的最少代價，再討論當前月份要雇傭多少人的最小代價，（本質就是遍歷所有的可能情況取最小）
三層回圈：
3.最小代價，當時設定為無窮大，但要將dp[0][0]確定為0，保證轉移方程的正常運行，
F - Largest Submatrix
熟悉的三步驟
1.本題i控制行，j控制列，（ok！）
2.子矩陣要求相同字母最多---->>>轉化為子矩陣面積最大---->>>轉化為子矩陣的長和寬最大，
（與子矩陣中數的和最大類似，都是采用壓縮行，重點對列進行DP的程序）
目標明確：壓縮行就是統計這一列連續的和自己相似的字母個數；對列的DP采用兩個while回圈（選定某個值，不斷從左邊確定所能到達的界限，然后是右邊），理解了好久，
3.初始化將能變成a（含本身）字母全變成a，不能的清0，對于b，c同理，
G - How many ways （運用遞回，遞回其實不難，我一直沒抽時間去學，所以還是怕）
所以順手學了吧，漫漫長夜
1.明確這個遞回函式滿足得功能（自己的目的）
2.確定遞回的結束邊界，執行到哪一步時退出回圈，
3.找出滿足的遞回方程，由于是對自身的小規模呼叫，注意引數的變化，
需要滿足的條件：
1.有遞回公式，分解為一個個和自身類似的小問題；
2.有確定的邊界，最后能得到一個確定的值，
（突然發現和區間DP好像好像，連需要滿足的條件都很類似，再結合做過的題目，發現好多題目都可用遞回解決，所以突然想回過頭用遞回重新做那些題目）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280645.html
標籤：其他
上一篇：2021春天梯賽個人總結和感悟
下一篇：第八周學習總結——區間dp的學習