正整数的摆动序列:dp
正整数的摆动序列
问题描述
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 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。
他是以前面和后面的部分来做和进行加和比较，4321初始化，奇数项就是从后面往前面进行比较，偶数项因为是要算比较小的，所以是从前面往后面数，而前面和后面数的结果要进行把前面的结果想加上，所以奇数项和偶数项他们的最后的结果所在的位置也是不相同的，这点要记住。
package 第二次蓝桥;
import java.util.Scanner;
public class 正整数的摆动序列 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
sc.close();
//因为是从1开始计算，而n,m+1，所以初始化出来的结果的m,n都要加2
int[][] dp=new int[m+2][n+2];
for(int i=1;i<=n;i++)
dp[1][i]=n-i+1;
//进行初始化，n(n-1-（n-2）
for(int i=2;i=1;j--)
dp[i][j]=(dp[i-1][j-1]+dp[i][j+1])%1000;
}else{
//从前往后算
for(int j=1;j<=n;j++)
dp[i][j]=(dp[i-1][j+1]+dp[i][j-1])%1000;
}
}
int anse= (m&1)==1? dp[m][1]:dp[m][n];
System.out.println(anse);
}
}
作者：weixin_44522477
