【ブルーブリッジカップ】パスゲーム(ダイナミックプランニング)

【問題の説明】
体育の授業を受ける時、小蛮の先生はよく学生たちを連れてゲームをします.今度、先生は学生たちを連れてパスゲームをします.
ゲームのルールはこうです.n人の同級生が円に立っていて、その中の一人の同級生が手にボールを持っていて、先生がホイッスルを吹くとパスを始めました.それぞれの学友はボールを自分の左右の2人の学友の中の1つ(左右の任意)に伝えることができて、先生が再びホイッスルを吹く時、パスは止まって、この時、ボールを持って伝わっていないあの学友は敗者で、みんなに1つの番組を披露します.
聡明な小蛮は面白い問題を提出した:いくつかの異なるパス方法が小蛮の手からパスしたボールを、m回パスした後、また小蛮の手に戻ることができる.2つのパスの方法は、異なる方法と見なされ、この2つの方法のうち、ボールを受け取った学生がボールの順序で構成されたシーケンスが異なる場合にのみ、異なる.例えば、3人の同級生が1番、2番、3番を持っていて、小蛮が1番だと仮定して、ボールが3回小蛮の手に戻る方法は1->2->3->1と1->3->2->1で、2種類あります.
入力フォーマット
1行で、スペースで区切られた2つの整数n,m(3<=n<=30,1<=m<=30)がある.
出力フォーマット
tは1行で、整数があり、題意に合致する方法数を表す.
サンプル入力
3 3
サンプル出力
2
データ規模と約定
40%のデータ満足:3<=n<=30,1<=m<=20
100%のデータ満足:3<=n<=30,1<=m<=30
ヒント:動的計画は、i回目の到達位置jのシナリオ数をF[i,j]で表すと、F[i,j]=F[i-1,j-1]+F[i-1,j+1となる.リングの処理もあります.

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int n = in.nextInt();
	int m = in.nextInt();
	int[][] dp = new int[m+1][n+1];
	dp[1][n] = 1;
	dp[1][2] = 1;
	for(int i=2;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j == 1)
			{
				dp[i][j] = dp[i-1][j+1]+dp[i-1][n];
			}else if(j == n){
				dp[i][j] = dp[i-1][j-1]+dp[i-1][1];
			}
			else {
				dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1];
			}
			
		}
	}
	System.out.println(dp[m][1]);
}
}