問題描述
　　如果一個序列滿足下面的性質，我們就將它稱為擺動序列：
　　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
樣例輸出

8

自己從來沒有做過動態規劃的題目，之前接觸動態規劃還是為了過算法的考試。所以說，坑總是要填的，遲早的事情，加油！

言歸正傳，這個題是要求滿足題目的序列個數。剛開始看到這個題，我的想法是，先自己試著手動做做，看看能不能發現什么。果然被我試出來了。動態規劃核心是構造一個表，根據已有的表格內容得到我們想要的結果。構造表的過程并不是一下子就成功的，期間我共想了兩種方式來構造，但是后來發現第一種方式是沒有辦法構造表的，因為在構造的過程中發現表間元素沒有什么關聯，所以換個思路，用另一個方法進行構造（有點遞歸的意思，但是并不是遞歸，也就是說當前數據依靠表格的之前的數據），給大家看一下我的表格構造：

擺動序列動規表格

?	002	003	004	005	006	007	008
002	2	0	0	0	0	0	0
003	6	2	0	0	0	0	0	?
004	12	8	2	0	0	0	0
005	20	20	10	2	0	0	0
006	30	40	30	12	2	0	0
007	42	70	70	42	14	2	0
008	56	112	140	112	56	16	2

通過這個表格不難發現規律。

（1）這個表格為什么從2開始呢？

因為根據題目要求，每行至少兩個正整數，所以不存在0和1的情況；

（2）這個表格根據什么構成？

是根據k值的不同，來看對應情況下的可能的序列個數。舉個例子：當k等于3的時候，考慮如果只有倆個數組成，可能多少種情況，如果有3個數組成，可能多少種情況。填入到表格中即可。如果學過排列組合，那不難發現彼此之間的關系，也因此得到了這個表格。

（3）有人可能通過排列組合的方式，不用構建表格就可以得到最后的結果，那還有必要建表格嗎？

有必要。如果是排列組合，舉例來說：k=8時，

這樣也可以算出最后的結果，但是乘法比加法的運算速度慢，此外，如果這么計算，其實重復性挺大的，利用表格，相當于記錄了路徑，之前算的東西可以直接拿來用，不用重新進行計算，更為快捷方便！

好，給大家看一下代碼，不到之處還希望大家可以批評指正：

#include<iostream> using namespace std; int main() {int k;int a[21][21];long result = 0;cin>>k;for(int i = 2; i <= k; i++){a[i][i] = 2;a[i][2] = i*(i-1);for(int j = 3; j < i; j++){a[i][j] = a[i-1][j]+a[i-1][j-1];}}for(int i = 2; i <= k; i++){result += a[k][i];}cout<<result;return 0; }

END。

總結

以上是生活随笔為你收集整理的蓝桥杯_算法训练_ALGO12_摆动序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。