JAva:ダイナミックプランニング-階段問題

JAva:段差問題
タイトルは、数ヶ月前に放映されたナンバーワンプレイヤーが火をつけることができなくなったことを描き、究極のAIを探求する研究者として、月神は自然にこの神劇を見に行った.興奮しすぎて、夜月神は奇妙な夢を見て、月神は自分が魔法をかけられた淵に落ちた夢を見て、月神はこの淵に登りたいと思っています.
深渊にはN层の阶段构成(1<=N<=1000)が知られており、月の神様は毎回2の整数次べき乗の阶段(1、2、4、...)を登ることができます.月の神様に、深渊から這い出す方法はいくつあるか教えてください.入力はM行です.(1<=M<=1000)
最初の行は、テストデータのセット数Mを入力します.
続いてM行があり、各行にNを入力して深淵を表す階段数出力記述:出力可能な深淵を這い出す方式例1入力:4 1 2 3 4出力:1 2 3 6解題構想:動的計画の思想、コイン交換問題との構想の差は多くないが、コイン交換問題の組み合わせは順序を考慮しないが、階段ジャンプ問題は階段を跳ぶ前後順序を考慮する必要がある.組合せを考慮する順序javaコードは以下の通りです.

import java.util.*;
public class Main{
    public static void main(String[] args){
    	Scanner in=new Scanner(System.in);
    	int n=in.nextInt();
    	int[] w=new int[n];
    	int[] step={1,2,4,8,16,32,64,128,256,512};
    	int[] res=new int[n];
    	for(int i=0;i<n;i++){
    		w[i]=in.nextInt();
    		res[i]=result(w[i],step,step.length);
    	}
    	for(int i:res) System.out.println(i);
	}
    public static int result(int k,int[] step,int n){
           int[] dp=new int[k+1];
           dp[0]=1;
//           for(int i=0;i
//        	   for(int j=step[i];j<=k;j++){
//        		   dp[j]=dp[j]+dp[j-step[i]];
//        	   }
//           }
           for (int i = 1; i <= k; ++i) {
   	        for (int j = 0; j < step.length && i >= step[j]; ++j) {
   	            dp[i] += dp[i - step[j]];
   	            dp[i] %= 1000000003L;
   	        }
   	    }
           return dp[k];
    }
}