[leetcode/lintcode 題解] 算法面試真題詳解：流浪劍客斯溫

描述

在物質位面“現實”中，有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

我們用dpidpi代表從星球00出發到達星球ii後擁有jj個金币的方案數。

• 設定初始狀态為在第0号星球，此時擁有m個币。dp0=1dp0=1。
• 我們考慮dpidpi的前繼狀态，可以發現，所有編号比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;
    }
}           

更多題解參考： 九章官網solution