FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[Original HTTPS Page]
MyAlgorithmNotes/DynamicProgramming at main · rzr8i/MyAlgorithmNotes · GitHub
rzr8i
/
MyAlgorithmNotes
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
MyAlgorithmNotes
/
DynamicProgramming
/
Copy path
Directory actions
More options
More options
Directory actions
More options
More options
Latest commit
History
History
History
Breadcrumbs
MyAlgorithmNotes
/
DynamicProgramming
/
Copy path
Folders and files
Name
Name
Last commit message
Last commit date
parent directory
..
CompanyPartyProblem
CompanyPartyProblem
ConvexTriangulation
ConvexTriangulation
LongestIncreasingSubsequence
LongestIncreasingSubsequence
README.md
README.md
README.md
Outline
Dynamic Programming
When to use?
when a problem can be broken down into
overlapping subproblems
(same subproblem appears many times)
when the problem has optimal substructure (optimal solution can be built from optimal solutions of subproblems)
Examples
Fibonacci sequence
Knapsack problem
Longest common subsequence
How it works?
solve subproblems once and store their results.
avoid recomputing the same subproblem over and over.
time complexity is usually polynomial (much better than exponential brute force)
space complexity can be optimized (e.g., keep only last two rows instead of full table).
Back
|
FazBrowse Home
|
New Git URL