摆动序列

问题描述

如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。
即 $a[2i] < a[2i-1]$ ， $a[2i+1] > 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。

Code

N = 1000
f = [[0] * N for _ in range(N)]


def DP():
    # 加入已知信息
    for i in range(1,n+1):
        f[1][i] = 1

    # DP
    for i in range(2,m+1):
        for j in range(1,n+1):
            if i % 2 == 0:
                k = j + 1
                while k <= n:
                    f[i][j] += f[i-1][k]
                    k += 1
            else:
                k = j - 1
                while k >= 1:
                    f[i][j] += f[i-1][k]
                    k -= 1
    res = 0
    for i in range(1,n+1):
        res += f[m][i]
    return res


if __name__ == "__main__":
    m, n = map(int, input().split())
    print(DP())