Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space.

#### Minimum Number of Multiplication in Matrix Multiplication

Given the dimensions of n matrices M1..Mn, what is the minimum number of multiplication in M1 x M2 x ... x Mn. Example: Suppose dimensions are given as [10, 30, 5, 60], meaning 3 matrices with dime ...
Berkan Teber
Published on Jan 15th, 2018

#### Paper Cut into Minimum Number of Squares

Given a paper of size A x B, the task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper. Example: When paper size is 36 x 30, the outpu ...
Berkan Teber
Published on Jan 15th, 2018

#### Number of Ways to Transform a String into a Substring

Given two sequences A and B, find out number of unique ways to transform sequence A into sequence B. Transformation means converting string A (by removing 0 or more characters) to string B. Examples ...
Berkan Teber
Published on Jan 15th, 2018

#### The Painter's Partition Problem

We have to paint n boards of length [A1, A2, ..., An]. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get this job done ...
Berkan Teber
Published on Jan 15th, 2018