1.“寄”数DP
例题 [SDOI2010]地精部落：
求n的排列，形成波浪，如：2 1 4 3（浪大小为一个点）
很容易想到dp[i][j]表示1~i的排列，开头（或结尾，一个道理）为j的排列数量
(F[][]为头为峰，G[][]为头为谷)
有三条性质：
*一个序列，交换两个不相邻的j,j-1,序列仍合法
*将序列 >=x的部分全部+1，仍合法
*将i=n-i+1，序列倒转
考虑F[i][j]的转移，若j-1与j不相邻，F[i][j]+=F[i]j-1
若相邻，则后面分成[1,j-1],[j+1，i]两段，后一段可由[j,i-1]整体+1得到
[1,j-1]+[j,i-1]正好是[1,i-1];