歡迎回到：遇見藍橋遇見你，不負代碼不負卿！
目錄
一、何為動態規劃DP
二、記憶化搜索
典例1.斐波那契數列
方法一：暴力遞回
方法二：記憶化搜索
變形題
典例2：爬樓梯（青蛙跳臺階）
方法一：暴力遞回
方法二：記憶化搜索
變形題
典例3.第N個泰波那契數
典例4.Function
三、遞推
1.遞回
2.遞推
典例5.骨牌問題
典例6.楊輝三角
典例7.數字三角形
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿，
【前言】
在學習動態規劃之前，我們必須要先掌握記憶化搜索和遞推，這兩塊東西搞好了之后，面對動態規劃那就容易多啦！好，接下來向鐵汁們詳細介紹這兩塊內容，走著，
哈哈，昨天在群里發現這張表清包，覺得很好玩，特意放到這里皮一下，嘿嘿，這下真的要開始咯，
一、何為動態規劃DP
動態規劃（英語：Dynamic programming，簡稱 DP），通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法， （是不是很像前面講解過的一種演算法——分治，其實可以認為動態規劃就是特殊的分治）
動態規劃常常適用于有重疊子問題和最優子結構性質的問題，并且記錄所有子問題的結果，因此動態規劃方法所耗時間往往遠少于暴力遞回解法，
使用動態規劃解決的問題有個明顯的特點，一旦一個子問題的求解得到結果，以后的計算程序就不會修改它，這樣的特點叫做無后效性，求解問題的程序形成了一張有向無環圖，動態規劃只解決每個子問題一次，具有天然剪枝的功能，從而減少計算量，
動態規劃有自底向上和自頂向下兩種解決問題的方式，自頂向下即記憶化搜索，自底向上就是遞推，
好，那么本文主要講解的記憶化搜索和遞推也就浮出水面了，下面詳細介紹（請放心，后面會詳細講解動態規劃的，這部分既重要又很難，所以需要慢慢去理解，）
二、記憶化搜索
記憶化搜索的本質：動態規劃，
記憶化搜索是動態規劃的一種實作方式，記憶化搜索是用搜索的方式實作了動態規劃，因此記憶化搜索就是動態規劃，
提問：
何為記憶化搜索？
回答：
顧名思義，記憶化搜索肯定也就和“搜索”脫不了關系， 前面講解的遞回、DFS和BFS想必大家都已經掌握的差不多了，它們有個最大的弊病就是：低效！原因在于沒有很好地處理重疊子問題，那么對于記憶化搜索呢，它雖然采用搜索的形式，但是它還有動態規劃里面遞推的思想，巧就巧在它將這兩種方法很好的綜合在了一起，簡單又實用，
記憶化搜索，也叫記憶化遞回，其實就是拆分子問題的時候，發現有很多重復子問題，然后再求解它們以后記錄下來，以后再遇到要求解同樣規模的子問題的時候，直接讀取答案，
其實可以淺顯的認為記憶化搜索就是簡單DP，因為實在是太像了，
下面詳細講解四道例題，讓大家深入理解上面的概念：
典例1.斐波那契數列
原題鏈接：力扣
題目描述：
示例1：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1示例2：
輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2方法一：暴力遞回
代碼執行：
class Solution {
public:
int fib(int n){
//方法一：暴力遞回
//找邊界
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return fib(n - 1) + fib(n - 2);
}
};不用多說，學校老師講遞回的時候似乎都是拿這個舉例，我們也知道這樣寫代碼雖然簡潔易懂，但是十分低效，低效在哪里？假設 n = 20，請畫出遞回樹：
很顯然，進行了大量的重復計算，雖然本題是一個很好的用來講解遞回的例子，但是嘞，本題在實際運用當中用遞回來做那就太不明智啦，所以，這里就需要引入一個帶有「備忘錄」的遞回，也就是前面所提到的記憶化搜索，下面看看具體怎么操作：
方法二：記憶化搜索
即然低效的原因是重復計算，那么我們可以造一個「備忘錄」，每次算出某個子問題的答案后別急著回傳，先記到「備忘錄」里再回傳；每次遇到一個子問題先去「備忘錄」里查一查，如果發現之前已經解決過這個問題了，直接把答案拿出來用，不要再耗時去計算了，
一般使用一個陣列充當這個「備忘錄」，當然你也可以使用哈希表（字典），思想都是一樣的，
這樣去處理的話就無需進行重復計算了，相比前面的暴力遞回就顯得高效明智得多，而且很容易理解，不信你看：
代碼執行：
class Solution {
public:
int fib(int n){
//方法三：記憶化搜索（簡單DP）
//找邊界
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
//需要定義一個大小為(n+1)的整形陣列，并且初始化為0
//之所以是n+1,是因為要使用到n這個下標
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < n+1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};當然也有這樣的變形，多了一個要求，很簡單的，大家看一下：
變形題
代碼執行：
//找邊界
if(n == 0)
return 0;
if(n == 1)
return 1;
vector<int> dp(n + 1, 0);//開辟一個大小為n+1的整形陣列（因為需要使用下標n），并且初始化為0
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < n+1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] = dp[i] % 1000000007;
}
return dp[n];
}實際上，這種解法和迭代的動態規劃非常相似，只不過這種方法叫做「自頂向下」，動態規劃叫做「自底向上」，
啥叫「自頂向下」？
注意我們剛才畫的遞回樹（或者說圖），是從上向下延伸，都是從一個規模較大的原問題比如說 f(20)，向下逐漸分解，直至 f(1) 和 f(2) 這兩個 base case，然后逐層回傳答案，這就叫「自頂向下」，
啥叫「自底向上」？
反過來，我們直接從最底下，最簡單，問題規模最小的 f(1) 和 f(2) 開始往上推，直到推到我們想要的答案 f(20)，這就是動態規劃的思路，這也是為什么動態規劃一般都脫離了遞回，而是由回圈迭代完成計算，
典例2：爬樓梯（青蛙跳臺階）
原題鏈接：力扣
題目描述：
示例1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂，
1. 1 階 + 1 階
2. 2 階示例2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂，
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階首先分析一下本題：
注意：這個題目問的是什么？
問的不是能爬多少次，而是有多少種方法能到最后一個臺階，
問題分析：
當n > 2時，第一次爬就有兩種不同的選擇：一是第一次只爬一級，此時爬法數目等于后面剩下的（n - 1）級臺階的爬法數目，即為f(n - 1); 還有一種選擇是第一次爬兩級，此時爬法數目等于后面剩下的（n - 2）級臺階的爬法數目，即為f(n - 2).
所以有：f(n) = f(n - 1) + f(n - 2)
當n == 1時，有1種爬法；
當n == 2時，有2種爬法；
當n == 3時，有3種爬法；
當n == 4時，有5種爬法，
是呀，這題跟斐波那契數列基本上一樣，不過這道題目需要思考一下，沒有斐波那契數列這么明顯，但是需要注意的是，遞回邊界還是有所不同的哦！
方法一：暴力遞回
代碼執行：
class Solution {
public:
int climbStairs(int n) {
//方法一：暴力遞回
//找邊界
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
};方法二：記憶化搜索
代碼執行：
class Solution {
public:
int climbStairs(int n) {
//方法二:記憶化搜索（簡單DP）
//找邊界
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
//定義一個大小為n+1的整型陣列，并且初始化為0
vector<int> dp(n+1, 0);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i < n+1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};變形題
其實就是多了一個要求...
代碼執行：
class Solution {
public:
int numWays(int n) {
//找邊界
if(n == 0 || n == 1)
return 1;
if(n == 2)
return 2;
vector<int> dp(n+1, 0);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i < n+1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] %= 1000000007;
}
return dp[n];
}
};典例3.第N個泰波那契數
原題鏈接：力扣
題目描述：
示例1：
輸入：n = 4
輸出：4
解釋：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4示例2：
輸入：n = 25
輸出：1389537代碼執行：
class Solution {
public:
int tribonacci(int n) {
//找邊界
if(n == 0)
return 0;
if(n == 1 || n == 2)
return 1;
//定義一個大小為n+1的整形陣列，并將其初始為0
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for(int i = 3; i < n+1;i++)
{
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];//遞推公式
}
return dp[n];
}
};上面這三道題是非常簡單的，理解了上面的題目，下面這道題肯定就會非常容易了，
典例4.Function
原題鏈接： Function - 洛谷
題目描述：
輸入格式：
輸入有若干行，并以?1,?1,?1結束，
保證輸入的數在[?9223372036854775808,9223372036854775807]之間，并且是整數，
輸出格式
輸出若干行，每一行格式：
w(a, b, c) = ans
思路：
本題重在理解題意，題目不難，但是要把題目多讀幾遍，
代碼執行：
#include <stdio.h>
#define LL long long
LL dp[25][25][25];
LL w(LL a, LL b, LL c)
{
//兩個特殊情況判斷
if(a <= 0 || b <= 0 || c <= 0)
return 1;
if(a > 20 || b > 20 || c > 20)
return w(20, 20, 20);
if(a < b && b < c)
{
if(dp[a][b][c-1] == 0)
{
dp[a][b][c-1] = w(a, b, c-1);
}
if(dp[a][b-1][c-1] == 0)
{
dp[a][b-1][c-1] = w(a, b-1 ,c-1);
}
if(dp[a][b-1][c] == 0)
{
dp[a][b-1][c] = w(a, b-1, c);
}
dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
}
else
{
if(dp[a-1][b][c] == 0)
{
dp[a-1][b][c] = w(a-1, b, c);
}
if(dp[a-1][b-1][c] == 0)
{
dp[a-1][b-1][c] = w(a-1, b-1 ,c);
}
if(dp[a-1][b][c-1] == 0)
{
dp[a-1][b][c-1] = w(a-1, b, c-1);
}
if(dp[a-1][b-1][c-1] == 0)
{
dp[a-1][b-1][c-1] = w(a-1, b-1, c-1);
}
dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b][c-1] + dp[a-1][b-1][c] - dp[a-1][b-1][c-1];
}
return dp[a][b][c];
}
int main()
{
LL a, b, c;
while(scanf("%lld%lld%lld", &a, &b, &c) != EOF)
{
if(a == -1 && b == -1 && c == -1)
return 0;//當輸入的值為-1 -1 -1時直接結束回圈
printf("w(%lld, %lld, %lld) = ", a, b, c);
printf("%lld\n", w(a, b, c));
}
}
三、遞推
看到“遞推”，大家肯定能聯想到“遞回”，好嘞，接下來向大家詳細講解遞推和遞回有哪些區別，
1.遞回
如果大家對于遞回部分掌握的不是很好的話可以看看我之前的博文哦，里面的基礎概念講解的很詳細，而且還配備大量練習題，
藍橋杯演算法競賽系列第二章——深入理解重難點之遞回（上）_安然無虞的博客-CSDN博客一、遞回是什么
https://blog.csdn.net/weixin_57544072/article/details/120836167
遞回是大問題轉化為小問題，不斷呼叫自身或不斷被間接呼叫的一類演算法，
1.遞回演算法的關鍵是要找出大問題和小問題的聯系----即找重復，進而使大問題的規模不斷減小，直至可以被直接解決，
2.遞回演算法的另一個關鍵點是終止條件----即找邊界，這個是十分重要的，
有時，遞回演算法的效率會很低，這時候就可以用上面所說的記憶化搜索，即建立一個陣列，用來記錄每次遞回得到的答案，這樣如果后面要繼續使用這個值的時候，就不用再次計算了，也就避免了重復計算問題，
2.遞推
部分定義和題解參考博客鏈接：
遞推演算法-五種典型的遞推關系_lybc2019的博客-CSDN博客_遞推法
遞推和遞回非常相似，
遞推是把問題劃分為若干個步驟，每個步驟之間，或者是這個步驟與之前的幾個步驟之間有一定的數量關系，可以用前幾項的值表示出這一項的值，這樣就可以把一個復雜的問題變成很多小的問題，
遞推演算法注意的是設定什么樣的遞推狀態，因為一個好的遞推狀態可以讓問題很簡單，最難的是想出遞推公式，一般遞推公式是從后面向前想，倒推回去，
典例5.骨牌問題
題目描述：
有 2*n的一個長方形方格，用一個1*2的骨牌鋪滿方格，請撰寫一個程式，試對給出的任意一個n(n>0), 輸出鋪法總數，
思路：
其實這道題目很簡單的，找到遞推公式即可，跟上面的爬樓梯問題很相似，這里就詳細分析一下：
n = 1 時，只有一種鋪法
n = 2 時，如下圖，有全部豎著鋪和橫著鋪兩種
n = 3 時，骨牌可以全部豎著鋪，也可以認為在方格中已經有一個豎鋪的骨牌，則需要在方格中排列兩個橫排骨牌（無重復方法），若已經在方格中排列兩個橫排骨牌，則必須在方格中排列一個豎排骨牌，如下圖，再無其他排列方法，因此鋪法總數表示為三種，
通過上面的分析，不難看出規律：f(3) = f(1) + f(2)所以可以的得到遞推關系：f(n) = f(n - 1) + f(n - 2)
代碼執行：
class Solution {
public:
int brand(int n) {
//找邊界
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
//定義一個大小為n+1的整型陣列，并且初始化為0
vector<int> dp(n+1, 0);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i < n+1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];//找出遞推關系
}
return dp[n];
}
};典例6.楊輝三角
原題鏈接：力扣
題目描述：
示例1：
輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例2：
輸入: numRows = 1
輸出: [[1]]思路：
本題比較簡單，很容易就能看出遞推關系，從第三行第二列開始，每個數是它左上方和右上方的數的和，
代碼執行：
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int> >ret(numRows);//定義一個二維陣列用于存放結果
//首先將第一列和最后一列元素全部賦值為1
for(int i = 0; i < numRows; i++)
{
ret[i].resize(i+1);//resize()的作用就是為一維陣列分配空間
ret[i][0] = ret[i][i] = 1;
//從第三行第二列開始有遞推關系：ret[i][j] = ret[i+1][j]+ret[i+1][j+1];
for(int j = 1; j < i; j++)
{
ret[i][j] = ret[i-1][j] + ret[i-1][j-1];
}
}
return ret;
}
};代碼中需要注意的是：vector 中的resize() 是重新分配空間的，
典例7.數字三角形
原題鏈接：[USACO1.5][IOI1994]數字三角形 Number Triangles - 洛谷
題目描述：
輸入格式：
第一個行一個正整數 n ,表示行的數目，
后面每行為這個數字金字塔特定行包含的整數，
輸出格式：
單獨的一行,包含那個可能得到的最大的和，
資料范圍：
1 ≤ n ≤ 1000，三角形數字值在 [0,100] 范圍內，
示例:
輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 輸出：
30思路：
本題采用倒推的方式：
假設func[i][j]表示的是從 i, j 到最后一層的最大路徑之和
當從頂層沿某條路徑走到第i層向第i+1層前進時，我們的選擇是沿其下兩條可行路徑中最大數字的方向前進，所以找出遞推關系：func[i][j] += max(func[i+1][j],func[i+1][j+1])；
注意：func[i][j]表示當前數字的值，func[i+1][j]和func[i+1][j+1]分別表示從i+1,j、i+1,j+1到最后一層的最大路徑之和；
最終func[0][0]就是所求
代碼執行：
#include<stdio.h>
#include<algorithm>
using namespace std;
int func[1005][1005] = {0};
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j <= i; j++)
{
scanf("%d", &func[i][j]);
}
}
//假設func[i][j]表示的是從i, j到最后一層的最大路徑之和
//找出遞推關系：func[i][j]+=max(func[i+1][j],func[i+1][j+1]);
//func[i][j]表示當前數字的值，func[i+1][j]和func[i+1][j+1]分別表示從i+1,j、i+1,j+1到最后一層的最大路徑之和
//最終func[0][0]就是所求
for(i = n - 2; i >= 0; i--)
{
for(j = 0; j <= i; j++)
{
func[i][j] += max(func[i+1][j], func[i+1][j+1]);
}
}
printf("%d\n", func[0][0]);
return 0;
}
四、藍橋結語：遇見藍橋遇見你，不負代碼不負卿，
又到了說再見的時候了，上面是動規引入部分，看起來不難，但其實動態規劃演算法難起來是真變態，后面會慢慢深入，不過藍橋幾乎不會考到特別難的動規，正常都是簡單DP，所以后面會有大量的練習側重于簡單DP，OK，今天到這就結束咯，886
求求兄弟姐妹們 · 賞俺個三連吧~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/386677.html
標籤：其他
上一篇：數學建模那些事兒