Dynamic Programming
Dynamic Programming
Given a flight itinerary consisting of starting city, destination city, and ticket price (2D list) - find the optimal price flight path to get from start to destination. (A variation of Dynamic Programming Shortest Path)
Given some coin denominations and a target value
M
, return the coins combination with the minimum number of coins.Time complexity:
O(MN)
, where N is the number of distinct type of coins.Space complexity:
O(M)
.
Given a set of numbers in an array which represent a number of consecutive days of Airbnb reservation requested, as a host, pick the sequence which maximizes the number of days of occupancy, at the same time, leaving at least a 1-day gap in-between bookings for cleaning.
The problem reduces to finding the maximum sum of non-consecutive array elements.
E.g.
Given a list of denominations (e.g.,
[1, 2, 5]
means you have coins worth $1, $2, and $5) and a target numberk
, find all possible combinations, if any, of coins in the given denominations that add up tok
. You can use coins of the same denomination more than once.
Last updated