{"id":7341,"date":"2020-09-05T17:55:52","date_gmt":"2020-09-06T00:55:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7341"},"modified":"2020-09-05T18:07:48","modified_gmt":"2020-09-06T01:07:48","slug":"leetcode-1575-count-all-possible-routes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1575-count-all-possible-routes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1575. Count All Possible Routes"},"content":{"rendered":"\n

You are given an array of distinct<\/strong> positive integers locations where locations[i]<\/code> represents the position of city i<\/code>. You are also given integers start<\/code>, finish<\/code> and fuel<\/code> representing the starting city, ending city, and the initial amount of fuel you have, respectively.<\/p>\n\n\n\n

At each step, if you are at city i<\/code>, you can pick any city j<\/code> such that j != i<\/code> and 0 <= j < locations.length<\/code> and move to city j<\/code>. Moving from city i<\/code> to city j<\/code> reduces the amount of fuel you have by |locations[i] - locations[j]|<\/code>. Please notice that |x|<\/code> denotes the absolute value of x<\/code>.<\/p>\n\n\n\n

Notice that fuel<\/code> cannot<\/strong> become negative at any point in time, and that you are allowed<\/strong> to visit any city more than once (including start<\/code> and finish<\/code>).<\/p>\n\n\n\n

Return the count of all possible routes from <\/em>start<\/code> to<\/em> finish<\/code>.<\/p>\n\n\n\n

Since the answer may be too large, return it modulo 10^9 + 7<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5\nOutput:<\/strong> 4\nExplanation:<\/strong> The following are all possible routes, each uses 5 units of fuel:\n1 -> 3\n1 -> 2 -> 3\n1 -> 4 -> 3\n1 -> 4 -> 2 -> 3\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> locations = [4,3,1], start = 1, finish = 0, fuel = 6\nOutput:<\/strong> 5\nExplanation: <\/strong>The following are all possible routes:\n1 -> 0, used fuel = 1\n1 -> 2 -> 0, used fuel = 5\n1 -> 2 -> 1 -> 0, used fuel = 5\n1 -> 0 -> 1 -> 0, used fuel = 3\n1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> locations = [5,2,1], start = 0, finish = 2, fuel = 3\nOutput:<\/strong> 0\nExplanation: <\/strong>It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> locations = [2,1,5], start = 0, finish = 0, fuel = 3\nOutput:<\/strong> 2\nExplanation:<\/strong> There are two possible routes, 0 and 0 -> 1 -> 0.<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> locations = [1,2,3], start = 0, finish = 2, fuel = 40\nOutput:<\/strong> 615088286\nExplanation: <\/strong>The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= locations.length <= 100<\/code><\/li>
  • 1 <= locations[i] <= 10^9<\/code><\/li>
  • All integers in locations<\/code> are distinct<\/strong>.<\/li>
  • 0 <= start, finish < locations.length<\/code><\/li>
  • 1 <= fuel <= 200<\/code><\/li><\/ul>\n\n\n\n
    Solution: DP<\/strong><\/h2>\n\n\n\n
    dp[j][f] := # of ways to start from city ‘start’ to reach city ‘j’ with fuel level f.<\/p>\n\n\n\n
    dp[j][f] = sum(dp[i][f + d])  d = dist(i, j)<\/p>\n\n\n\n
    init: dp[start][fuel] = 1<\/p>\n\n\n\n
    Time complexity: O(n^2*fuel)
    Space complexity: O(n*fuel)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int countRoutes(vector& x, int start, int finish, int fuel) {\n    constexpr int kMod = 1e9 + 7;\n    const int n = x.size();    \n    vector> dp(n, vector(fuel + 1));\n    dp[start][fuel] = 1;\n    for (int f = fuel; f > 0; --f)\n      for (int i = 0; i < n; ++i) {\n        if (!dp[i][f] || abs(x[i] - x[finish]) > f) continue; \/\/ pruning.\n        for (int j = 0; j < n; ++j) {\n          const int d = abs(x[i] - x[j]);                    \n          if (i == j || f < d) continue;\n          dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % kMod;\n        }\n      }\n    return accumulate(begin(dp[finish]), end(dp[finish]), 0LL) % kMod;        \n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def countRoutes(self, x: List[int], start: int, finish: int, fuel: int) -> int:    \n    @lru_cache(None)\n    def dp(i, f): # ways to reach |finsh| from |i| with |f| fuel.\n      if f < 0: return 0\n      return (sum(dp(j, f - abs(x[i] - x[j])) \n                 for j in range(len(x)) if i != j) + (i == finish)) % (10**9 + 7)\n    return dp(start, fuel)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217],"class_list":["post-7341","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7341","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7341"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7341\/revisions"}],"predecessor-version":[{"id":7344,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7341\/revisions\/7344"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7341"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7341"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7341"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}