演算法入門經典競賽第二版 動態規劃（抽象篇）

1抽象的動態規劃

a.何為抽象的動態規劃，就是用dp[i][j]i表示一個數，j表示另一個數，然后思考狀態轉移；
例題：出堆疊順序
思路：
f(i,j)表示出堆疊順的總數：
i表示為堆疊外的車數,j表示堆疊內的車數;
由2種狀態:注意狀態表示不能跳躍
狀態跳躍就是這個狀態轉移后又轉移到下一個狀態：
這題有2種情況：
一：里面的車出去一輛，外面不進來；
二：里面的車不出去，外面進來一駕車；
跳躍就是里面的車出去，外面進來一輛；
仔細觀察會發現這個情況就是一 二合在一起的情況
公式：

f[i][j]+=dfs(i,j-1);//外面進來，里面出去一個
	 f[i][j]+=dfs(i-1,j+1);//外面進來一輛

#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N][MAX_N];
ll dfs(int i,int j)//i表示堆疊外的數量 ,j是堆疊內的車數 
{
	if(f[i][j]) return f[i][j];//如果記憶化搜索里面有值的話就直接回傳；
	if( i == 0 ) return 1;//如果堆疊外里面沒車了，就放回1，堆疊內全部出去
	if(j > 0 ) f[i][j]+=dfs(i,j-1);
	 f[i][j]+=dfs(i-1,j+1); 
	return f[i][j];
}
int main()
{
	scanf("%d",&n);
	printf("%lld",dfs(n,0));
	return 0;
}

總結：
這里運用到一個劉佳汝老師說的記憶化搜索技巧：
每次遞回的時候，畫出搜索樹的時候會有狀態計算重復，比如說f（1，2）在f(2,1)的時候和f(1,3)的時候都呼叫過了，每次呼叫都要重復計算浪費時間；不如把計算過的數值保存下來；
用一個陣列保存

ll f[MAX_N][MAX_N];
	if(f[i][j]) return f[i][j];//如果之前計算過的話，就直接回傳

邊界處理:

if(j > 0 ) f[i][j]+=dfs(i,j-1);//如果j大于0的話，就可以從j-
1轉移：
	 f[i][j]+=dfs(i-1,j+1); 

方法二
遞推：
思路：

1，狀態表示：dp[i][j] i表示堆疊內的數，j表示堆疊外的數；
2.邊界化：i==j dp[i][j]=dp[i][j-1];//如果堆疊內和堆疊外的方案，就里面不動，外面進來一個
3. 初始化 dp[i][0]=1; 外面沒車了，里面出去一個就好了
公式：
dp[i][j]=dp[i-1][j]+dp[i+1][j-1]

代碼：

#include <iostream>
using namespace std;
long long  dp[10010][10010];//i是堆疊外的車，j是堆疊內的車 
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<=n;++i)
	{
		dp[0][i]=1;
	}
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)
		{
			if(j==0) //堆疊內沒車 
			{
				dp[i][j]=dp[i-1][1];
				continue;
			}
			if(i==j) dp[i][j]=dp[i-1][j];
			else dp[i][j]=dp[i][j-1]+dp[i-1][j] ;
		}
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

2.題目：
一個游戲每個人都可以給左邊或者右邊的人可以由左邊到右邊的人轉過來：
思路：
1.抽象表示出來，dp[i][j]表示考慮第i圈到第j個人手里：

2.公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];//每次都是上一圈考慮前面一個和上一圈后面一個人
3.初始化:dp[0][1]=1;轉了0次，表示第1個人;
4.邊界化：
if(j == 1) 1號人是上一次的2號和n 號過來
else if(j == n) n號人是上一次1號和n-1號過來；
5，答案是表示為：
dp[m][1]；
6.回圈順序：i-1先完成i從小到大完成：
代碼：

#include <iostream>
using namespace std;
long long dp[10010][10010];
int main()
{
	int n,m;
	cin>>n>>m;
	dp[0][1]=1;
	for(int i = 1;i<= m;++i)
	{
		for(int j = 1;j <= n;++j)
		{
			if(j == 1)
			{
				dp[i][j]=dp[i-1][2]+dp[i-1][n];
			 } 
			 else if(j == n)
			 {
			 	dp[i][j]=dp[i-1][1]+dp[i-1][n-1];
			 }
			 else
			 dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
		}
	}
	cout<<dp[m][1]<<endl;
	return 0;
}

3.題目；
有個珠子每個珠子可以和前面后面的合并，合并后該位置變為前后2個珠子合并的乘積：
求最大值：
比如輸入：
8
-9 -5 - 4 -2 4 -5 -4 2
輸出 73；
思路：
1.dp[i][j]表示考慮到i這個位置，j表示狀態 0 是不合并，1是合并；
2.公式：
dp[i][0]不合并的話就是可以順便搞，選前面最大值就可以dp[i][0]=max(dp[i-1][0],dp[i-1][1])
dp[i][1]//合并的話就是當前加上乘積

#include <iostream>
using namespace std;
int dp[10010][2];
int w[10010];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>w[i];
	}
	dp[1][0]=0;
	for(int i=2;i<=n;++i)
	{
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
		dp[i][1]=dp[i-1][0]+w[i]*w[i-1];
	}
	cout<<max(dp[n][0],dp[n][1])<<endl;
	return 0;
	
}

總結：
動態規劃的抽象：
1，用狀態表示出來：
技巧：有的時候一個狀態如果***只有2種狀態***的話，可以直接利用dp[i][j]i表示考慮到i了，j=0表示一種狀態，j=1表示另一種狀態；
2.抽象的動態規劃也有邊界化問題和初始化；
3.注意初始化循序：