1 public class test 2 { 3     public static void main(String[] args) 4     { 5         Scanner input = new Scanner(System.in); 6         int n = input.nextInt(); 7         int k = input.nextInt(); 8         int[] dp = new int[n + 1]; 9         System.out.println(uniquePath(n, k, dp));10     }11     12     //Iterative13     public static int uniquePath(int n, int k, int[] dp)14     {15         //第一个位置不使用16         //dp[1] 至 dp[k]赋值 17         for(int i = 1; i <= Math.min(n, k); i++)  //保证n < k时仍能正常运行 18         {19             for(int j = 1; j < i; j++)20                 dp[i] += dp[j];21             dp[i]++;22         }23         24         //dp[k + 1] 至 dp[n]赋值25         for(int i = k + 1; i <= n; i++)26             for(int j = i - k; j < i; j++)27                 dp[i] += dp[j];28         29         return dp[n];30     }31     32     //Recursive33     public static int uniquePath(int n, int k, int[] dp)34     {35         //dp的第一个位置不使用36         if(n <= k)37         {38             for(int i = 1; i < n; i++)39             {40                 if(dp[i] == 0)41                     dp[i] = uniquePath(i, k, dp);42                 dp[n] += dp[i];43             }44             dp[n]++;45             return dp[n];46         }47         48         for(int i = n - k; i <= n - 1; i++)49         {50             if(dp[i] == 0)51                 dp[i] = uniquePath(i, k, dp);52             dp[n] += dp[i];53         }54         return dp[n];55     }56 }