A Plan for Mastering DP (Dynamic Programming)

Basics

More, if needed:

https://en.wikipedia.org/wiki/Optimal_substructure

https://en.wikipedia.org/wiki/Overlapping_subproblems

Optimal substructure—optimal solution can be constructed from optimal solutions of its subproblems

Overlapping sub-problems—problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems

Learn in depth

https://www.geeksforgeeks.org/solve-dynamic-programming-problem/

	Typically, all the problems that require to 

		maximize or 

		minimize certain quantity or 

		counting problems that say to count the arrangements under certain condition or 

		certain probability problems

			can be solved by using Dynamic Programming.



	1. Identify if the problem is a DP problem.

	2. Decide a state for the problem.

	3. Find a relation between 		previous states to reach the current state.

		---------------------------------------------------------------------------------------------------------------------------------------

		1   3   5                        state(n)   arrangements   to get   sum as n                                       

		---------------------------------------------------------------------------------------------------------------------------------------

		in 2d

		it can be 1d                                                                              

		---------------------------------------------------------------------------------------------------------------------------------------

			0  1   2   3   4   5   6   7

		1   0  1                         state(1)   1,

		2         1                      state(2)   1,1

		3            2                   state(3)   1,1,1           3,

		4               3                state(4)   1,1,1,1         3,1         1,3

		5                  5             state(5)   1,1,1,1,1       3,1,1       1,3,1       5,    1,1,3

		6                     8          state(6)   1,1,1,1,1,1     3,1,1,1     1,3,1,1     5,1   1,1,3,1     1,1,1,3     3,3    1,5

		7                        12      state(7)   1,1,1,1,1,1,1   3,1,1,1,1   1,3,1,1,1   5,1,1 1,1,3,1,1   1,1,1,3,1   3,3,1  1,5,1   1,1,1,1,3   3,1,3   1,3,3   1,1,5

		---------------------------------------------------------------------------------------------------------------------------------------

										 state(n)   state(n-1) +   state(n-3)    +            state(n-5)                           

		---------------------------------------------------------------------------------------------------------------------------------------

https://www.geeksforgeeks.org/tabulation-vs-memoization/

https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/

https://www.geeksforgeeks.org/dynamic-programming-vs-divide-and-conquer/

decision tree - Don’t have overlapping sub-problems - not dynamic programming problem - Divide and Conquer Example: Binary Search

decision graph

minimum edit distance/ levenshteinDistance

				EACH cell number in the matrix is being calculated based on PREVIOUS ones.

					SO TABULATION technique

						(filling the cache in bottom-up direction) is being applied here.



			""	k	i	t	t	e	n				""	s	a	t	u	r	d	a	y						a

		""	0	1	2	3	4	5	6			""	0	1	2	3	4	5	6	7	8						..

		s	1	1	0	0	0	0	0			s	1	0	1	2	3	4	5	6	7				this	top	

		i	2	0	2	0	0	0	0			u	2	1	1	2	2	3	4	5	6		b	..	left	from here	

		t	3	0	0	1	1	0	0			n	3	2	2	2	3	3	4	5	6						

		t	4	0	0	1	1	0	0			d	4	3	3	3	3	4	3	4	5						

		i	5	0	1	0	0	0	0			a	5	4	3	4	4	4	4	3	4						

		n	6	0	0	0	0	0	1			y	6	5	4	4	5	5	5	4	3					a == b	this

		g	7	0	0	0	0	0	0																	a != b	this +1

																											

																										min(top+1, left+1, this/ this +1)