演算法入門競賽經典 動態規劃

1.動態規劃的條件：
所謂動態規劃就是把一個問題，劃分成每一個小問題，從第一個小問題不斷推進到后面的子問題；每一個階段可以分為這樣的想法：
每個階段包括2種東西，一個是決策，就是當前這個階段要怎么做，寧一個叫做狀態，就是用一個標志表示當前狀態
2.
一維陣列的動態規劃；
a.最長單調子序列：
輸入一串陣列輸出單調遞增的最大子序列：
比如
輸入132 4 56
子序列1 2 4 5 6最大輸出的應該是 5；
思路：
定義dp[i]表示a陣列里面最長單調的長度；
每次要判斷一下這個尾巴是否大于前面的一個，如果比前面一個大就加上一；

b.題目：洛谷
思路：
這樣的題目我們這樣想，用dp[i]表示當前感染了多少人；
我們考慮最后一輪，最后一次論感染的人就是上一輪的人數加上新感染的人，得出遞推公式；
*dp【i】=dp[i-1]x+dp[i-1];

/*
1.dp[i]表示感染了i個人；
2.dp[i]=dp[i-1]+x*dp[i-1]; 
3.dp[0]=1
*/
#include <iostream>
using namespace std;
long long  dp[10010];
int main()
{
	int x,n;
	cin>>x>>n;
	dp[0]=1;
	for(int i=1;i<=n;++i)
	{
		dp[i]=x*dp[i-1]+dp[i-1];
	}
	cout<<dp[n]<<endl;
}

跳馬問題：
題目
思路:
我們用dp[i][j]表示當前的陣列走到方法數；
dp[i][j]就是左邊過來的方法 左邊過來可以是i-2，j-1
i-2，j+1;
i-1,j+2;
i-1,j-2;
dp[i][j]=dp[i-2][j-1]+dp[i-2][j+1]+dp[i-1][j+2]+dp[i-1][j-2];
動態規劃要注意初始化；
dp[0][0]=1;
判斷邊緣條件；
在最上邊如何都走不到n，因為不能橫著走；
所以都為0；
下面要轉移，所以要保證陣列不會越界，需要判斷；
動態轉移的時候要注意之前的狀態已經被賦值的話才可以轉移，不然后面更新不了，如果前面沒有賦值的話；
既是
dp[i][j要計算的是i-2；
所以在計算i的時候i-2已經有值了，不用在計算；
所以回圈是i從0到大的算；
注意回圈順序；

for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0&&j!=0) dp[i][j]=0;//一開始在最上面的話因為不能走直線所以就為0； 
        
            	else{
                if(i>1){
                    if(j>0)dp[i][j]+=dp[i-2][j-1];//如果i>1，而且j>0表示可以從a【i-2】【j-1】轉移 
                    if(j!=m)dp[i][j]+=dp[i-2][j+1];//如果不是終點繼續移動 
                }
                if(j>1)dp[i][j]+=dp[i-1][j-2];//同上面的道理 
                if(j<m-1)dp[i][j]+=dp[i-1][j+2];
            
			}
        }

代碼：

#include<iostream>
using std::cin;
using std::cout;

int dp[20][20];
int main(){
    int n,m;
    cin>>m>>n;
    dp[0][0]=1;//開始位置初始化為1； 
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0&&j!=0) dp[i][j]=0;//一開始在最上面的話因為不能走直線所以就為0； 
        
            	else{
                if(i>1){
                    if(j>0)dp[i][j]+=dp[i-2][j-1];//如果i>1，而且j>0表示可以從a【i-2】【j-1】轉移 
                    if(j!=m)dp[i][j]+=dp[i-2][j+1];//如果不是終點繼續移動 
                }
                if(j>1)dp[i][j]+=dp[i-1][j-2];//同上面的道理 
                if(j<m-1)dp[i][j]+=dp[i-1][j+2];
            
			}
        }
    }
    cout<<dp[n][m];
    return 0;
}

方法2：dfs（）搜索：
代碼：

#include <iostream>
using namespace std;
int dp[10010][10010];
int d[4][2]={{1,2},{1,-2},{2,1},{2,-1}};
int ans=0,n,m,dx,dy;
bool in(int x,int y)
{
	return x>=0&&x<=m&&y>=0&&y<=n;
}
void dfs(int x,int y)
{
	if(x==m&&y==n)
	{
		ans++;
		return ;
	}
	for(int i=0;i<4;++i)
	{
		dx=x+d[i][0];
		dy=y+d[i][1];
		if(in(dx,dy)) dfs(dx,dy);
	}
}
int main()
{

	cin>>n>>m;
	dfs(0,0);
	cout<<ans;
 } 

想法：
從開頭位置開始dfs搜索，如果搜到終點的話，就把ans++，退出；
水題！！！；
注意位置陣列，馬的走法是【1，2】，【2，1】，【-1，2】，【2，-1】馬的走法可以記為1 2 的組合
3.數的計算
題目：我們要求找出具有下列性質數的個數(包含輸入的正整數 nn)，

先輸入一個正整數 nn(n \le 1000n≤1000),然后對此正整數按照如下方法進行處理：

不作任何處理；

在它的左邊加上一個正整數,但該正整數不能超過原數的一半；

加上數后,繼續按此規則進行處理,直到不能再加正整數為止，

比如6的時候：
滿足條件的數為

6，16，26，126，36，136
思路：
1.模擬直接暴力：
從1開始選，選到該數字的一半；
每個加上去的位置前面如果還可以分解就繼續分解；
比如4的時候
4就是 從 1開始選 14，24然后 24的時候2又可以分開為1 2 4這樣又可以在2的左邊加上去，
直接2個回圈遞回就可以：
代碼：

#include<cstdio>
using namespace std;
int n,cnt=1;
void func(int x)
{
    for(int i=1;i<=x/2;i++){
        cnt++;
        func(i);
    }//一開始本身就是一種方案，每個位置選進來后都呼叫這個函式，看看前面位置能不能選進來；
}
int main(){
    scanf("%d",&n);
    func(n);
    printf("%d\n",cnt);
}

放法2；
可以這樣想
定義f（n）為數字n的方法；
f（4）可以看成如下的方法
4
14
24
124
畫出搜索樹如下：

推出規律為
if（i%2==0) f[n]=f[n-1]+f[n/2];
else f[n]=f[n-1];
代碼：

#include <iostream>
using namespace std;
long long  f[10010];
int main()
{
	f[0]=f[1]=1;
	int n,cnt=1;
	cin>>n;
	for(int i=2;i<=n;++i)
	{
		if(i%2==0) f[i]=f[i-1]+f[i/2];
		else f[i]=f[i-1];
	}
	cout<<f[n];
}

好了差不多了 每天繼續加油