九章算法 | 微软面试题：流浪剑客斯温

[hakunamatata11]

描述

在物质位面“现实”中，有 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;
    }
}

更多题解参考