Library for Studying Dynamic Programming
Project description
Library for Studying Dynamic Programming
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
Installation
pip install dynamic-programming
Sample Usage
>>> 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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
dynamic-programming-0.0.2.tar.gz
(17.9 kB
view hashes)
Built Distribution
Close
Hashes for dynamic-programming-0.0.2.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9fc9d43538cd8fdbfe41f316a3257eb191683f8daa8f5d962ed9e15d325ef052 |
|
MD5 | 90765bbdc81c30c1fbddf21ec762ccc1 |
|
BLAKE2b-256 | 6c9680d4820f75f769c5ddf653ae1e931adc4c240b69a6cecf3670fbed2e997a |
Close
Hashes for dynamic_programming-0.0.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 342d3da153140caabf3f7eab8fa9108686bfaa49060e8cee43aa154980a71130 |
|
MD5 | 49bcaf46aef04049547bc45a22abfce3 |
|
BLAKE2b-256 | 8eefe4bf750d811b9cf1d29e4c41b0ba2793c92128f7e7bcaf2f4bf25c79969c |