正整數的擺動序列
問題描述
如果一個序列的奇數項都比前一項大，偶數項都比前一項小，則稱為一個擺動序列。即 a[2i]a[2i]。
小明想知道，長度為 m，每個數都是 1 到 n 之間的正整數的擺動序列一共有多少個。
輸入格式
輸入一行包含兩個整數 m，n。
輸出格式
輸出一個整數，表示答案。答案可能很大，請輸出答案除以10000的餘數。
樣例輸入
3 4
樣例輸出
14
樣例說明
以下是符合要求的擺動序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
評測用例規模與約定
對于 20% 的評測用例，1 <= n, m <= 5；
對于 50% 的評測用例，1 <= n, m <= 10；
對于 80% 的評測用例，1 <= n, m <= 100；
對于所有評測用例，1 <= n, m <= 1000。
這裡附上亓老闆的提高時間效率的一些[小技巧](https://blog.csdn.net/qq_43422111/article/details/105326623)
package 省模拟賽;
import java.util.Scanner;
public class 正整數的擺動序列 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
sc.close();
//dp[i][j] i表示第多少位，j表示一個分界線
//奇數行就是大于j的方案數，偶數行就是小于j的方案數
//奇數要比前面的大，是以要大于的，偶數要比前面的小，是以要小于的
int[][] dp = new int[m+2][n+2];
//初始化邊界
for (int i = 1; i <=n; i++) {
dp[1][i]=n-i+1;
}
for(int i = 2; i <= m; i++)
if((i&1)==1){
//奇數的話是要比前面大的,是以用倒序
for(int j = n; j >= 1; j--){
dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;
}
}
else{
for(int j = 1; j <= n; j++){
dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;
}
}
//判斷奇偶從此我要改成這個了，一位位運算确實快
//m&1，就是把m換成二進制看看最後一位是不是1，如果是1證明就是奇數，如果是0證明是偶數
int result = (m & 1)==1 ? dp[m][1] : dp[m][n];
System.out.println(result);
}
}