Name	Name	Last commit message	Last commit date
parent directory ..
comb	comb
edit-dist	edit-dist
knapsack	knapsack
lcs	lcs
lis	lis
mcm	mcm
mss	mss
tri	tri
C(n,k).cpp	C(n,k).cpp
README.md	README.md
comb(n,k).c	comb(n,k).c
edit-distance.cpp	edit-distance.cpp
knapsack-geeksforgeeks.c	knapsack-geeksforgeeks.c
knapsack.cpp	knapsack.cpp
knapsack2.cpp	knapsack2.cpp
lcs.c	lcs.c
lcs.cpp	lcs.cpp
lcs_annapurna.c	lcs_annapurna.c
lcs_annapurna.cpp	lcs_annapurna.cpp
lcs_infoarena.cpp	lcs_infoarena.cpp
lis.c	lis.c
lis.in	lis.in
lis.out	lis.out
lis_cses_big O(N log N).cpp	lis_cses_big O(N log N).cpp
lis_cses_big_O(n^2).cpp	lis_cses_big_O(n^2).cpp
match_words.c	match_words.c
match_words.in	match_words.in
match_words.out	match_words.out
match_words2.in	match_words2.in
mss.c	mss.c
rucsac.in	rucsac.in
triangle-problem-botorog.cpp	triangle-problem-botorog.cpp
triangle.in	triangle.in
triangle.out	triangle.out

Dynamic Programming

Dynamic Programming, like the divide-and-conquer method, solves problemes by combining the solutions to subproblems. "Programming" in this context refers to a tabular method, not to writing computer code. As we saw in DivideEtImpera algorithms partion the problem into dijoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming applies when the subproblems overlap-that is, when subproblems share subsubproblems. In this context, a divideEtImpera algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achive the optimal value.

When developing a dynamic programming algorithm, we follow a sequence of four steps: