Algorithms/Dynamic Programming - Revision history

Admin: Restore binomial section; remove duplicate fuzzy string matching section; fix swapped insert/delete recurrence formulas; fix pseudocode base case; clarify loop bounds in binomial pseudocode; fix typos (boundary→boundary, numbr→number) (via update-page on MediaWiki MCP Server)

2026-06-09T04:54:18Z

Restore binomial section; remove duplicate fuzzy string matching section; fix swapped insert/delete recurrence formulas; fix pseudocode base case; clarify loop bounds in binomial pseudocode; fix typos (boundary→boundary, numbr→number) (via update-page on MediaWiki MCP Server)

Show changes

Admin: Fix swapped Insert/Delete recurrence labels; fix broken base case; rename helper functions for clarity (via update-page on MediaWiki MCP Server)

2026-06-09T04:53:23Z

Fix swapped Insert/Delete recurrence labels; fix broken base case; rename helper functions for clarity (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 04:53, 9 June 2026
Line 13:		Line 13:
	Most efficient way: specify the order of evaluation in such a way that the results that are needed are always available. No caching necessary. It's a bit trivial once you reach this point, but it is still dynamic programming - you're just specifying the order in which to evaluate the sub-problems so that you always have the information you need.		Most efficient way: specify the order of evaluation in such a way that the results that are needed are always available. No caching necessary. It's a bit trivial once you reach this point, but it is still dynamic programming - you're just specifying the order in which to evaluate the sub-problems so that you always have the information you need.

	===~~Binomial dynamic programming~~ example===		===Fuzzy string matching example===

	Skiena ~~uses the binomial coefficient as~~ an ~~example of a problem with a single expression that can be evaluated, but that single expression will cause integer overflow~~.		The next example Skiena covers is an important one: fuzzy string matching.

	~~Instead: use identity,~~		We are trying to pattern-match the string P in a larger text T.

	~~<math>~~		To do approximate string matching, we must begin with a cost function. The cost function assigns a cost to each possible modification of our original string.
	~~\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}~~
	~~</math>~~

	~~and the base cases~~:		3 classes of edits:
			* Substitution (turning one letter into another)
			* Insertion
			* Deletion

	~~<math>~~		To find the minimum cost function to turn our pattern P into something in the original text T, we need to work backwards: from the ending point, work backwards 1 edit at a time.
	~~\binom{p}{0} =~~ 1
	~~</math>~~

	~~<math>~~		Maintain a table:
	~~\binom{p}{1} = p~~		* D(i,j) is the distance (the number of differences) between P1, P2, ..., Pi and the segment of T ending at j
	~~</math>~~		* D(i,j) is the minimum of the three possible ways to extend the current string
			* In other words, it is the minimum of the following:

	<math>		Substitution: if <math>P_i = T_j</math> then <math>D(i-1, j-1)</math>, otherwise <math>D(i-1, j-1) + 1</math>
	~~\binom{p}{p}~~ = 1
	</math>

	~~To implement this~~, ~~we can build a table~~/~~array, which will contain Pascal's triangle...~~		Insert: <math>D(i, j-1) + 1</math>

	~~Left column~~: m, ~~top column: n~~		Delete: <math>D(i-1, j) + 1</math>

	~~Now the order of operations is to fill in the edges of Pascal's triangle (the base cases) first~~		Pseudocode for program:
	* Initialize column 0 = 1
	* Initialize diagonal = 1

	~~Now loop over each row and each column~~ of ~~the row to compute the binomial coefficient~~:		<pre>
			# Non-Dynamic Programming Version of Fuzzy String Matching
			def string_compare(s, t, i, j):

			# Base cases
			if i == 0:
			return j
			if j == 0:
			return i

			# Option: Match
			match = string_compare(s, t, i-1, j-1) + match_cost(s[i], t[j])

	~~<pre>~~		# Option: Insert
	~~for~~ i = 1 ~~to n~~:		insert = string_compare(s, t, i, j-1) + indel_cost(t[j])
	~~for j~~ = 1 to i:
	~~calculate binomial coefficient~~		# Option: Delete
			delete = string_compare(s, t, i-1, j) + indel_cost(s[i])

			# Pick minimum of these
			return min(match, insert, delete)
	</pre>		</pre>

			But this is horribly inefficient. Why? Because it does not memoize. This means that it is repeating the same tasks over and over again.

	===Fuzzy string matching example===		===Fuzzy string matching example===

Admin: /* Racing Gems */

2019-02-13T06:29:25Z

Racing Gems

← Older revision		Revision as of 06:29, 13 February 2019
Line 152:		Line 152:
	{{Main\|Racing Gems}}		{{Main\|Racing Gems}}

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/dynamic-programming/racing-gems		Link: https://git.charlesreid1.com/cs/java/src/master/dynamic-programming/racing-gems

	==Maximum Value Contiguous Subsequence==		==Maximum Value Contiguous Subsequence==

Admin: /* Maximum Value Contiguous Subsequence */

2019-02-13T06:29:13Z

Maximum Value Contiguous Subsequence

← Older revision		Revision as of 06:29, 13 February 2019
Line 158:		Line 158:
	{{Main\|Maximum Value Contiguous Subsequence}}		{{Main\|Maximum Value Contiguous Subsequence}}

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/dynamic-programming/max-val-seq		Link: https://git.charlesreid1.com/cs/java/src/master/dynamic-programming/max-val-seq

	==Letter Coverage==		==Letter Coverage==

Admin: /* Letter Coverage */

2019-02-13T06:29:01Z

Letter Coverage

← Older revision		Revision as of 06:29, 13 February 2019
Line 164:		Line 164:
	{{Main\|Letter Coverage}}		{{Main\|Letter Coverage}}

	Link: https://charlesreid1.com~~:3000~~/cs/five-letter-words/src/master/word_coverage		Link: https://git.charlesreid1.com/cs/five-letter-words/src/master/word_coverage

	=Resources=		=Resources=

Admin: /* Longest Increasing Subsequence */

2019-02-13T06:28:52Z

Longest Increasing Subsequence

← Older revision		Revision as of 06:28, 13 February 2019
Line 146:		Line 146:
	{{Main\|Longest Increasing Subsequence}}		{{Main\|Longest Increasing Subsequence}}

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/dynamic-programming		Link: https://git.charlesreid1.com/cs/java/src/master/dynamic-programming

	==Racing Gems==		==Racing Gems==

Admin: /* Links to Videos */

2017-08-16T01:24:59Z

Links to Videos

← Older revision		Revision as of 01:24, 16 August 2017
Line 204:		Line 204:
	[[Category:CS]]		[[Category:CS]]
	[[Category:Skiena]]		[[Category:Skiena]]
			[[Category:Dynamic Programming]]

Admin: /* Maximum Value Contiguous Subsequence */

2017-08-16T01:01:50Z

Maximum Value Contiguous Subsequence

← Older revision		Revision as of 01:01, 16 August 2017
Line 159:		Line 159:

	Link: https://charlesreid1.com:3000/cs/java/src/master/dynamic-programming/max-val-seq		Link: https://charlesreid1.com:3000/cs/java/src/master/dynamic-programming/max-val-seq

			==Letter Coverage==

			{{Main\|Letter Coverage}}

			Link: https://charlesreid1.com:3000/cs/five-letter-words/src/master/word_coverage

	=Resources=		=Resources=

Admin: /* Links to Videos */

2017-08-09T21:24:50Z

Links to Videos

← Older revision		Revision as of 21:24, 9 August 2017
Line 166:		Line 166:
	===Links to Videos===		===Links to Videos===

	Dynamic programming 1: Fibonacci, shortest paths: https://www.youtube.com/watch?v=OQ5jsbhAv_M		Dynamic programming 1: Fibonacci, shortest paths: [https://www.youtube.com/watch?v=OQ5jsbhAv_M YouTube video link]

	Dynamic programming 2: Blackjack: https://www.youtube.com/watch?v=ENyox7kNKeY		Dynamic programming 2: Blackjack: [https://www.youtube.com/watch?v=ENyox7kNKeY YouTube video link]

	Dynamic programming 3: Parenthesization, edit distance, knapsack: https://www.youtube.com/watch?v=ocZMDMZwhCY		Dynamic programming 3: Parenthesization, edit distance, knapsack: [https://www.youtube.com/watch?v=ocZMDMZwhCY YouTube video link]

	Dynamic programming 4: guitars, tetris, super mario: https://www.youtube.com/watch?v=tp4_UXaVyx8		Dynamic programming 4: guitars, tetris, super mario: [https://www.youtube.com/watch?v=tp4_UXaVyx8 YouTube video link]

	==MIT Open Courseware 6.046==		==MIT Open Courseware 6.046==

Admin: /* Links to Videos */

2017-08-09T21:24:25Z

Links to Videos

← Older revision		Revision as of 21:24, 9 August 2017
Line 178:		Line 178:
	===Links to Videos===		===Links to Videos===

	The topic of dynamic programming is covered in the ~~MIT 6.046 open courseware playlist:~~ https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp		The topic of dynamic programming is covered in the [https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp MIT 6.046 open courseware playlist]

	The course begins with dynamic programming, by covering the divide and conquer approach for finding a convex hull: https://www.youtube.com/watch?v=EzeYI7p9MjU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=2		The course begins with dynamic programming, by covering the divide and conquer approach for finding a convex hull: [https://www.youtube.com/watch?v=EzeYI7p9MjU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=2 YouTube video link]

	It continues with a divide and conquer approach for matrix algebra and Fast Fourier Transforms: https://www.youtube.com/watch?v=iTMn0Kt18tg&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=4		It continues with a divide and conquer approach for matrix algebra and Fast Fourier Transforms: [https://www.youtube.com/watch?v=iTMn0Kt18tg&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=4 YouTube video link]

	It then covers divide and conquer for van Emde Boas trees: https://www.youtube.com/watch?v=hmReJCupbNU&index=6&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp		It then covers divide and conquer for van Emde Boas trees: [https://www.youtube.com/watch?v=hmReJCupbNU&index=6&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp YouTube video link]

	Recitation with more dynamic programming examples: https://www.youtube.com/watch?v=krZI60lKPek&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=12		Recitation with more dynamic programming examples: [https://www.youtube.com/watch?v=krZI60lKPek&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=12 YouTube video link]

	Advanced dynamic programming: https://www.youtube.com/watch?v=Tw1k46ywN6E&index=14&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp		Advanced dynamic programming: [https://www.youtube.com/watch?v=Tw1k46ywN6E&index=14&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp YouTube video link]

	Dynamic programming for all pairs, shortest paths: https://www.youtube.com/watch?v=NzgFUwOaoIw&index=15&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp		Dynamic programming for all pairs, shortest paths: [https://www.youtube.com/watch?v=NzgFUwOaoIw&index=15&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp YouTube video link]