最詳細的動态規劃解決 藍橋杯 擺動序列

動态規劃的題目一般都是先找到變化的量，再找到狀态轉移方程，最後建立一個dp表即可。但對于動态規劃的難點就是如何尋找狀态轉移方程。下面我會很詳細的一步步的說明如何找到狀态轉移方程。

問題描述
　　如果一個序列滿足下面的性質，我們就将它稱為擺動序列：
　　1. 序列中的所有數都是不大于k的正整數；
　　2. 序列中至少有兩個數。
　　3. 序列中的數兩兩不相等；
　　4. 如果第i – 1個數比第i – 2個數大，則第i個數比第i – 2個數小；如果第i – 1個數比第i – 2個數小，則第i個數比第i – 2個數大。
　　比如，當k = 3時，有下面幾個這樣的序列：
　　1 2
　　1 3
　　2 1
　　2 1 3
　　2 3
　　2 3 1
　　3 1
　　3 2
　　一共有8種，給定k，請求出滿足上面要求的序列的個數。
輸入格式
　　輸入包含了一個整數k。（k<=20）
輸出格式
　　輸出一個整數，表示滿足要求的序列個數。
           

          首先，要把這道題的題目條件讀懂，前三點都很容易了解，關鍵點是最後一點，看起來很繞，其實稍微了解一下，它說的就是假如有三個數，由題目3的條件可知它們都是大小不同的，也就是把這三個數比作 大 中 小 。将它們進行排列，隻有（中 小 大）和（中 大 小）這兩種情況滿足要求，換句話說大的那個數和小的那個數順序随意，但是中間大小的那個數字一定要在最右邊。

          剛剛我們講的是3個數的情況，推廣到多個數字的時候，就是其中的每三個數都滿足上述情況的排列，才算是一種合格的排列。

          讀完了題目後，我們就要開始找變化的量，首先k肯定是一個變化的量毋庸置疑。但動态規劃一般都有兩個變化的量，觀察題目第一點，我們發現最大的數字也在變化。既然這樣我們就先建立一張二維表，橫坐标為這個序列的長度，縱坐标為這個序列的最大值。

len=2	len=3	len=4	len=5
k=2
k=3
k=4
k=5

          這樣一張dp表就建立好了。下面我們就要試着往dp表裡填一些東西來試圖找到某種轉移的規律。首先當k為2的情況，自然是隻有1、2和2、1兩種情況，當k為3時題目已經給出樣例，我們不妨先填進去。

len=2	len=3	len=4	len=5
k=2	2
k=3	6	2
k=4
k=5

          但這樣好像還不夠，這張表裡有用的資料還是太少了，我們很難通過它來找到規律，是以我們可以試着把k=4的情況算手動算出來。

len=2	len=3	len=4	len=5
k=2	2
k=3	6	2
k=4	12	8	2
k=5

          以上的工作都是準備工作，通過這些準備工作，我們能夠得到一張比較全面的dp表，這樣做有利我們尋找規律。現在我們通過這張建構好的表來看看，首先看第一列，2，6，12這幾個數字好像有點規律，但我們還是要結合題意來思考，長度為2的時候，最大值為2的時候，有（1，2）、（2，1）兩種情況。當長度為2的時候，最大值為3的時候有（1，2）、（1，3）、（2，1）、（2，3）、（3，1）、（3，2）6種情況，由此我們好像發現，當長度為2的時候，就是1-k中任意挑兩個數字進行排列，為了確定我們的猜想是對的，我們可以算k=4時， C 4 2 C_4^2 C42​ 等于12，和表中的資料對應上了。

          但是，原因是什麼呢？ 其實原因很簡單，隻有2個數字的情況對于題目要求的第四點是都成立的，是以就成了一個排列問題。dp表中的第一列都會等于 C k 2 C_k^2 Ck2​

          迄今為止，我們隻差把中間部分的遞推方程給解出來即可，我們先觀察k=4,len=3情況。因為它周圍都有資料，我們把它情況列出來，

（2，3，1）（2，1，3）（2，1，4）（2，4，1）

（3，1，4）（3，4，1）（3，2，4）（3，4，2）

共8種排列，而對于它上面一列k=3,len=3來說，上面一列肯定是下面一列的子集，因為最大值增加了，排列肯定會包括原來的那部分，是以dp方程為

dp[i][j]=dp[i-1][j]+一個數字

如果對資料比較敏感的或者比較有經驗的人肯定已經發現了這是數就是

dp[i-1][j-1] 。 但原因是什麼呢？

          原因就是我們dp表中的i行j列其實就相當于在i-1行j-1列中插入一個k，以k=3，len=3舉例，它就相當于在（1，2）和（2，1）排列裡面插入3這個數字，插入後要滿足題目第四點給出的情況，我們隻能是在（2，1）裡面插，因為在（1，2）裡面插無論如何也不能滿足中間的數在最左邊，在這裡這個中間數是2，無論是插在左邊（3，1，2）還是插在中間（1，3，2）還是插在右邊（1，2，3）都不滿足要求。而對于（2，1）來說隻能插在最右邊和中間，因為K是最大的數字，K不能在左邊。是以有兩種插入情況。

推廣到更大的len來說，有一半的排列是不能插的，而對于另一半來說，這個最大的數可以插在最右邊和倒數第二個位置。如果再往左邊的話，就會不滿足題目要求了。是以相當于(i-1)(j-1)的情況除2再乘2等于本身。得出最後的遞推方程：

                                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[][] dp=new int[n+1][n+1];
		for(int i=2;i<=n;i++) {
			dp[i][2]=i*(i-1);
		}
		for(int i=2;i<=n;i++) {
			for(int j=3;j<=n;j++) {
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			}
		}
		int sum=0;
		for(int i=2;i<=n;i++)
			sum+=dp[n][i];
		System.out.println(sum);
	}
}