Dynamic Programming is a method used to solve complex problems by breaking down into simpler subproblems. It is applicable when the problem has overlapping subproblems and optimal substructure properties. The core idea is to store the results of subproblems to avoid redundant computations.
Let’s delve into some famous DP cases, breaking down each concept into small pieces step by step.
1. Frog Problem (Optimal Substructure)
Problem Statement:
Given a series of stones, each with a certain height, calculate the minimum stamina required for a frog to reach the goal. The frog can jump to the next stone or skip one stone.
Variables:
ground
: Array representing the height of each stone.height
: Array of heights.stamina
: Energy or cost required to jump between stones.
Objective:
Minimize the total stamina required to reach the last stone.
DP Approach:
We use a DP array dp[i]
where dp[i]
represents the minimum stamina required to reach the ith
stone.
Here is the important point for the DP that the dp array holds final outputs in this time stamina
.
Steps:
 Initialization:
dp[0] = 0
: No cost(consume some stamina) to stay on the first stone.dp[1] = abs(height[1]  height[0])
: Cost(consume some stamina) to jump to the second stone.

Recurrence Relation:
For each stone
i
from 2 ton
1 2 3 4
oneStoneJump = dp[i  1] + abs(height[i]  height[i  1]); skipOneStoneJump = dp[i  2] + abs(height[i]  height[i  2]); dp[i] = min(oneStoneJump, skipOneStoneJump);

Template Function (Relaxation):
It is a modeling strategy that aims to solve a difficult problem by approximating it with a nearby problem that is easier to solve.
https://en.wikipedia.org/wiki/Relaxation_(approximation)


PullBased and PushBased Approaches:
 PushBased: Calculate
dp[i]
from previous points (dp[i1]
anddp[i2]
).


 PushBased: Update future points from the current point.


Memoization:
Store intermidiate results to avoid redundant calculations
2. Knapsack Problem
Problem Statement:
Given N
items, each with a weight and a value, find the maximum value you can obtain without exceeding a total weight W
.
Variables:
N
: Number of items.weights
: Array of weights of items.values
: Array of values of items.W
: Maximum allowable weight.
Objective:
Maximize the total value without exceeding the weight W
.
DP Approach:
We use DP array dp[i][w]
where dp[i][w]
represents the maximum value achievable with the first i
items and weight w
.
Steps:
 Initialization:


 Recurrence Relation:
For each item i
and weight w
:


3. Edit Distance
Problem Statement:
Given two strings, calculate the minimum number of operations (insert, delete, substitue) required to transform one string into another.
Variables:
str1
,str2
: The two strings to be transformed.
Objective:
Minimize the number of operations to transform str1
into str2
DP Approach:
We use a DP array dp[i][j]
when dp[i][j]
represents the minimum number of operations required to transform the first i
characters of str1
to the first j
characters of str2
.
Steps:
 Initialization
prepare a table referirng each defined strings 0 case.
i represents first str, and j represents second str.


 Recurrence Relation:
For each character i
in str1
and j
in str2
.


 When
str1[i  1] == str2[j  1]
: if the characters are the same, no edit operation is needed, so the cost remains the same as for the previous characters,dp[i  1][j  1]
.  When
str1[i  1] != str2[j  1]
: If the characters are diffrent, it requires one of the three operations(insert, delete, substitute) to make the characters match. Hence, the example adds 1 to the minimum cost of the three possible previous operations:dp[i  1][j]
: Represents deleting a character fromstr1
(moving up in the DP table)dp[i][j  1]
: Represents inserting a character intostr1
(moving left in the DP table)dp[i  1][j  1]
: Represents substituting a character instr1
with a character fromstr2
(moving diagonally in the DP table)
Example:
Consider transforming str1 = "konokuniwo"
to str2 = "kaetai"
:
dp[0][0]
todp[0][6]
anddp[1][0]
todp[10][0]
are initialized based on the length of the substrings. For
dp[1][1]
:str1[0] == str2[0]
(‘k’ == ‘k’), sodp[1][1] = dp[0][0] = 0
.
 For
dp[1][2]
:str1[0] != str2[1]
(‘k’ != ‘a’), sodp[1][2] = 1 + min(dp[0][2], dp[1][1], dp[0][1]) = 1 + min(2, 0, 1) = 1
.
The final value dp[len(str1)][len[str2]
will give the minimum number of operations required to transform str1
into str2
.
Summary
Dynamic programming is such a powerful technique for solving optimization problems by breaking them down into simpler subproblems and storing the results of thses subproblems to avoid redundant computations that we can achieve efficent and effective solutions.