Dynamic programming Flashcards
how is Dynamic programming similar to devide-counquer
both solve problems by combining the solutions to subproblems.
what type of proplems dose DP solve
solve optimization problems
why is dynamic programming important
It applies when the subproblems overlap ( subproblems are dependent).
.
divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems.
and this why DP exiest
A dynamic programming algorithm solves each subsubproblem…….
once and then saves its answer in a table (array), thereby avoiding the work of re-computing the answer every time it solves each subproblem
Dynamic-programming algorithm consists of a sequence of four steps:
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from computed information
in what style fose DP solve proplems
bottom-up
how can DP solve fibbonaici
by saving information of f(0),f(2),f(4)and not compute them every time istade it just retrive it from an array
what big o of Fibonacci Series
O (2ˆn) “exponential time
time complexity of fibonacci series when solved in DP style
O(n)instade of O(2ˆn)
The two key ingredients that an optimization problem must have in order to apply dynamic programming
1-Optimal substructure
-A problem exhibits optimal substructure if an optimal solution to the problem contains within its
-optimal solutions to subproblems.
In dynamic programming, we build an optimal solution to the problem from optimal solutions to subproblems.
.
2-Overlapping subproblems
-The space of subproblems must be “small” in
-Dynamic-programming algorithms
-take advantage of overlapping subproblems by solving each subproblem once and then storing the solution
Some applications of dynamic programming :
- Matrix-chain multiplication
- Knapsack problem
- Longest common subsequence problem
goal of knapsack proplem
to get the maximum total profit that we can carry is no more than some fixed number W.
talk about the Two versions of the knapsack problem
1Fractional knapsack problem
Items are divisible: you can take any fraction of an item.
Some instances can be solved with greedy algorithm.
0-1 knapsack problem
Items are indivisible: You either take an item or not.
Some instances can be solved with dynamic programming.
Number of items n=3
Maximum capacity W=50
how to choose most value item
andfind the result table
It is called a “fractional” problem because….
a fraction of each item can be taken.
how is 0-1 Knapsack Problem: brute-force approach done
write the algorthim of 0-1 knapsack
what the input and output of knapsack algorthim
solve
in Constructing an optimal solutionTo select the items that make the max profit
there is two ways mention them
whats the algorthim to find the optimal soultion from given table
solve
