Skip to content

Instantly share code, notes, and snippets.

@lbvf50mobile
Last active July 31, 2020 18:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lbvf50mobile/4287b62e14f5918ce80b9cc0d271d316 to your computer and use it in GitHub Desktop.
Save lbvf50mobile/4287b62e14f5918ce80b9cc0d271d316 to your computer and use it in GitHub Desktop.
Leetcode: 1029. Two City Scheduling.
# Leetcode: 1029. Two City Scheduling.
# https://leetcode.com/problems/two-city-scheduling/
# Runtime: 224 ms, faster than 9.30% of Ruby online submissions for Two City Scheduling.
# Memory Usage: 10.2 MB, less than 100.00% of Ruby online submissions for Two City Scheduling.
# @param {Integer[][]} costs
# @return {Integer}
def two_city_sched_cost(costs)
@dp = {}
@costs = costs
top_down(0,costs.size/2, costs.size/2)
end
def top_down(i, a, b)
return 0 if 0 == a && 0 == b
arr = [i, a, b]
return @dp[arr] if @dp[arr]
if 0 == a
x = @costs[i][1] + top_down(i+1,a,b-1)
return @dp[arr] = x;
end
if 0 == b
x = @costs[i][0] + top_down(i+1,a-1,b)
return @dp[arr] = x;
end
x = [@costs[i][1] + top_down(i+1,a,b-1),@costs[i][0] + top_down(i+1,a-1,b)].min
@dp[arr] = x;
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment