_ _
DP is suitable for a particular kind of problem (computation) structure: the subproblems are highly overlapping (usually with exponential time complexity, like 2^n) and the recurrence relation can be clearly defined.
In this library, I provide implementations of two major DP approaches -- (1) top-down (recursion + memoization); (2) bottom-up (tabulation) -- for some well-known DP problems, including:
- Fibonacci_Numbers
- House_Robber
- Min_Cost_Climbing_Stairs
- Maximum_Subarray
- Best_Time_to_Buy_and_Sell_Stock
- Coin_Change
- Word_Break
- Decode_Ways
pip install dynamic-programming>>> from DP import Fibonacci_Numbers as fib >>> F = fib() >>> F.explanation() # this will show the code and some explanations >>> F.top_down(n = 10) 55 >>> F.bottom_up(n = 10) 55
>>> from DP import House_Robber as robber >>> r = robber() >>> r.explanation() # this will show the code and some explanations >>> r.top_down(nums = [3, 10, 3, 1, 2, 4, 10, 2, 44, 98]) 120 >>> r.bottom_up(nums = [3, 10, 3, 1, 2, 4, 10, 2, 44, 98]) 120
>>> from DP import Min_Cost_Climbing_Stairs as climb >>> c = climb() >>> c.explanation() # this will show the code and some explanations >>> c.top_down(cost = [3, 10, 3, 1, 2, 4, 10, 2, 44, 98]) 57 >>> c.bottom_up(cost = [3, 10, 3, 1, 2, 4, 10, 2, 44, 98]) 57
>>> from DP import Maximum_Subarray as maxsub >>> m = maxsub() >>> m.explanation() # this will show the code and some explanations >>> m.top_down(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4, 9, -2, 10, 15, -3, -4]) [4, -1, 2, 1, -5, 4, 9, -2, 10, 15] has the largest sum = 37. >>> m.bottom_up(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4, 9, -2, 10, 15, -3, -4]) [4, -1, 2, 1, -5, 4, 9, -2, 10, 15] has the largest sum = 37.
>>> from DP import Best_Time_to_Buy_and_Sell_Stock as stock >>> s = stock() >>> s.explanation() # this will show the code and some explanations >>> s.top_down(prices=[7, 1, 5, 3, 6, 4, 2, 10, 2, 3, 9, 1]) 9 >>> s.bottom_up(prices=[7, 1, 5, 3, 6, 4, 2, 10, 2, 3, 9, 1]) 9
>>> from DP import Coin_Change as coin >>> c = coin() >>> c.explanation() # this will show the code and some explanations >>> c.top_down(coins=[1, 5, 10, 25], amount=150) 6 >>> c.bottom_up(coins=[1, 5, 10, 25], amount=150) 6
>>> from DP import Word_Break as wordbreak >>> w = wordbreak() >>> w.explanation() # this will show the code and some explanations >>> w.top_down(s = "codingisfunpythonisgreat", wordDict = ["coding", "is", "fun", "python", "great"]) True >>> w.bottom_up(s = "codingisfunpythonisgreat", wordDict = ["coding", "is", "fun", "python", "great"]) True
>>> from DP import Decode_Ways as decode >>> d = decode() >>> d.explanation() # this will show the code and some explanations >>> d.top_down(s = "12812823") 8 >>> d.bottom_up(s = "12812823") 8