题意

在物质位面“现实”中，有n+1个星球，分别为星球0，星球1，……，星球n。

每一个星球都有一个传送门，通过传送门可以直接到达目标星球而不经过其他的星球。

不过传送门有两个缺点。

第一，从星球i通过传送门只能到达编号比i大，且与i的差不超过limit的星球。

第二，通过传送门到达星球j，需要cost[j]个金币。

现在，流浪剑客斯温到达星球0后身上有m个金币，请问他有多少种方法通过传送门到达星球n？

样例

给出 n = 1, m = 1, limit = 1, cost = [0, 1]，返回 1。
解释：
方案1：星球0→星球1

给出 n = 1, m = 1, limit = 1, cost = [0, 2]，返回 0。
解释：
无合法方案

给出 n = 2, m = 3, limit = 2, cost = [0, 1, 1]，返回 2。
解释：
方案1：星球0→星球1→星球2

方案2：星球0→星球2
给出 n = 2, m = 3, limit = 2, cost = [0, 3, 1],返回 1。
解释：
方案1：星球0→星球2

注意事项

1 <= n <= 50, 0 <= m <= 100, 1 <= limit <= 50, 0 <= cost[i] <= 100。
由于cost[0]没有意义，题目保证cost[0] = 0。

1.解题思路

  这道题肯定使用动态规划来解决，解决动态规划的问题通常来说，难点在于动态规划方程怎么推导。
  首先我们定义一个二维的dp[m + 1][n + 1]，其实dp[i][j],表示有i那么的钱，到达j的次数，所以这个问题求解的是dp[m][n]的值
  其次,将dp[i][0]初始化为1，默认到0都为1次。
  此时我们需要求解i~n范围的值。当剑客到达i星球，它上一个的星球在[min, i)范围里面，其中max = Math.max(i - limit, 0)。然后我们来遍历从这个范围里面到i星球，如果这个星球能够到达i星球，那么使i星球的次数加上到达这个星球的次数。

2.代码

    public long getNumberOfWays(int n, int m, int limit, int[] cost) {
        int dp[][] = new int[m + 1][n + 1];
        //初始化dp数组
        for(int i = 0; i <= m; i++){
            
            dp[i][0] = 1;
        }
        for(int i = 1; i <= n; i++){
            int max = Math.max(0, i - limit);
            for(int j = max; j < i ; j++)
            {
                //从cost[i]开始判断，因为之前的肯定不能调到i星球
                for(int k = cost[i]; k <= m; k++){
                    dp[k][i] += dp[k - cost[i]][j];
                }
            }
        }
        return dp[m][n];
    }