描述

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

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

不过传送门有两个缺点。

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

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

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

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

在线评测地址

样例 1

比如 n = 15, 返回一个字符串数组：

输入: n = 1 m = 1,  limit = 1 cost = [0, 1] 输出: 1 解释: 方案 1：星球 0→星球 1  

样例 2

输入: n = 1 m = 1 limit = 1 cost = [0,2] 输出: 0 解释: 无合法方案  

算法：dp

我们用 dp[i][j]dp[i][j]代表从星球 00 出发到达星球 ii 后拥有 jj 个金币的方案数。

• 设置初始状态为在第 0 号星球，此时拥有 m 个币。dp[0][m]=1dp[0][m]=1 。
• 我们考虑 dp[i][j]dp[i][j]的前继状态，可以发现，所有编号比 i 小，且差在 limit 之内的都能转移过来，并且转移过程消耗 cost[i]cost[i]的币，所以对它的前继状态的方案数累加。
• 可列出状态转移方程如下所示，

• 最后因为要求总方案数，对于 sven 在第 nn 号星球的所有剩余金币数量求和即可。答案

复杂度分析

• 时间复杂度 O(n∗m∗limit)O(n∗m∗limit)
• 空间复杂度 O(n∗m)O(n∗m)
  • 就是 dpi所有的状态数

public class Solution {     /**      * @param n: the max identifier of planet.      * @param m: gold coins that Sven has.      * @param limit: the max difference.      * @param cost: the number of gold coins that reaching the planet j through the portal costs.      * @return: return the number of ways he can reach the planet n through the portal.      */     public long getNumberOfWays(int n, int m, int limit, int[] cost) {         //          long[][] dp = new long[n + 1][m + 1];         for (int i = 0; i < m; i++) {             dp[0][i] = 0;         }         dp[0][m] = 1;         for (int i = 1; i <= n; i++) {             for (int j = 0; j <= m; j++) {                 dp[i][j] = 0;                 for (int t = Math.max(0, i - limit); t <= i - 1; t++) {                     if (j + cost[i] <= m) {                         dp[i][j] += dp[t][j + cost[i]];                     }                 }             }         }         long ans = 0;         for (int i = 0; i <= m; i++) {             ans += dp[n][i];         }         return ans;     } }  

更多题解参考

大佬有話說 (0)