Concepts of Dynamic Programming
- Rust
The Fibonacci number
This can be directly translated into the following Rust code using recursion:
pub fn recursive_fibonacci(n: usize) -> usize {
if n == 0 || n == 1 {
return n;
}
recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)
}The code is easily comprehensible, but the runtime of it is rather poor.
graph TD;
F5(F5);
F5-->F5_F4(F4);
F5-->F5_F3(F3);
F5_F4-->F5_F4_F3(F3);
F5_F4-->F5_F4_F2(F2);
F5_F4_F3-->F5_F4_F3_F2(F2);
F5_F4_F3-->F5_F4_F3_F1(F1);
F5_F4_F3_F2-->F5_F4_F3_F2_F1(F1);
F5_F4_F3_F2-->F5_F4_F3_F2_F0(F0);
F5_F4_F2-->F5_F4_F2_F1(F1);
F5_F4_F2-->F5_F4_F2_F0(F0);
F5_F3-->F5_F3_F2(F2);
F5_F3-->F5_F3_F1(F1);
F5_F3_F2-->F5_F3_F2_F1(F1);
F5_F3_F2-->F5_F3_F2_F0(F0);
The above graph demonstrates that the function call recursive_fibonacci(5)
already involves a lot of redundant calculations, such as
recursive_fibonacci(3) and recursive_fibonacci(2).
At this point we should take a step back. Lets reiterate
what we already know. In order to calculate
This way we don't need to calculate a subproblem multiple times. The code for a primitive calculation storing all calculated values could like as follows.
pub fn array_fibonacci(n: usize) -> usize {
let mut vector = vec![0; n + 1];
vector[0] = 0;
vector[1] = 1;
for i in 2..=n {
let x = vector[i - 1];
let y = vector[(i - 2)];
vector[i] = x + y;
}
vector[n]
}At this point there is one more optimization that could me made regarding
its memory usage. In order to calculate
pub fn dynamic_fibonacci(n: usize) -> usize {
let mut x = 0;
let mut y = 1;
for _i in 0..n {
let t = y;
y += x;
x = t;
}
x
}Binomial Coeeficients can be calculated using the following formula,
where
The naive approach would be using recursion:
pub fn recursive_binomial(n: usize, k: usize) -> usize {
if n == k || k == 0 {
return 1;
}
recursive_binomial(n - 1, k - 1) + recursive_binomial(n - 1, k)
}The above recursive code can again be visualized using a graph.
graph TD;
5C3(5C3);
5C3-->5C3_4C2(4C2);
5C3-->5C3_4C3(4C3);
5C3_4C2-->5C3_4C2_3C1(3C1);
5C3_4C2-->5C3_4C2_3C2(3C2);
5C3_4C3-->5C3_4C3_3C2(3C2);
5C3_4C3-->5C3_4C3_3C3(3C3);
5C3_4C2_3C1-->5C3_4C2_3C1_2C0(2C0);
5C3_4C2_3C1-->5C3_4C2_3C1_2C1(2C1);
5C3_4C2_3C1_2C1-->5C3_4C2_3C1_2C1_1C0(1C0);
5C3_4C2_3C1_2C1-->5C3_4C2_3C1_2C1_1C1(1C1);
5C3_4C2_3C2-->5C3_4C2_3C2_2C1(2C1);
5C3_4C2_3C2-->5C3_4C2_3C2_2C2(2C2);
5C3_4C2_3C2_2C1-->5C3_4C2_3C2_2C1_1C0(1C0);
5C3_4C2_3C2_2C1-->5C3_4C2_3C2_2C1_1C1(1C1);
5C3_4C3_3C2-->5C3_4C3_3C2_2C1(2C1);
5C3_4C3_3C2-->5C3_4C3_3C2_2C2(2C2);
5C3_4C3_3C2_2C1-->5C3_4C3_3C2_2C1_1C0(1C0);
5C3_4C3_3C2_2C1-->5C3_4C3_3C2_2C1_1C1(1C1);
Applying the learnings from above we can calculate the binomial coefficients using a matrix:
The code for populating the matrix would look as follows.
pub fn matrix_binomial(n: usize, k: usize) -> usize {
let mut matrix = vec![vec![0; k + 1]; n + 1];
for i in 1..=n {
for j in 0..=k {
if i == j || j == 0 {
matrix[i][j] = 1;
} else {
let val = matrix[i - 1][j - 1] + matrix[i - 1][j];
matrix[i][j] = val;
}
}
}
matrix[n][k]
}Now there is one more thing to consider. In order to calculate a row
pub fn dynamic_binomial(n: usize, k: usize) -> usize {
let mut vec1 = vec![0; k + 1];
let mut vec2 = vec![0; k + 1];
for i in 0..=n {
for j in 0..=k {
if i == j || j == 0 {
vec1[j] = 1;
} else {
vec1[j] = vec2[j - 1] + vec2[j];
}
}
vec1.swap_with_slice(&mut vec2);
}
vec2[k]
}The trinomial coefficients can be calculated using the below function with
Again the recursive code can be easily obtained from the mathematical formula.
pub fn recursive_trinomial(n: i32, k: i32) -> i32 {
if k.abs() == n {
return 1;
} else if k.abs() > n {
return 0;
}
return recursive_trinomial(n - 1, k - 1)
+ recursive_trinomial(n - 1, k)
+ recursive_trinomial(n - 1, k + 1);
}This time we are going to skip the graph and we are looking straight onto the matrix calculating the values. The matrix can be easily filled by going row by row and column by column over it and applying the aforementioned rules.
Effectively you only need this half of the matrix:
An example of how that could be done using code is shown below.
pub fn matrix_trinomial(n: i32, k: i32) -> i32 {
let mut matrix = vec![vec![0; (n + 1) as usize]; (n + 1) as usize];
for i in 0..=n {
for j in 0..=n {
if i == j {
matrix[i as usize][j as usize] = 1;
} else if j < i {
let val = matrix[(i - 1) as usize][(j - 1).abs() as usize]
+ matrix[(i - 1) as usize][j as usize]
+ matrix[(i - 1) as usize][(j + 1) as usize];
matrix[i as usize][j as usize] = val;
}
}
}
return matrix[n as usize][k as usize];
}The same memory optimizations from above can be applied here as well:
pub fn dynamic_trinomial(n: i32, k: i32) -> i32 {
let mut vec1 = vec![0; (n + 1) as usize];
let mut vec2 = vec![0; (n + 1) as usize];
for i in 0..=n {
for j in 0..=n {
if i == j {
vec1[j as usize] = 1;
} else if j < i {
let val = vec2[(j - 1).abs() as usize]
+ vec2[j as usize]
+ vec2[(j + 1) as usize];
vec1[j as usize] = val;
}
}
vec1.swap_with_slice(&mut vec2);
}
return vec2[k as usize];
}Given two sequences
Using the above formula we can successively populate a matrix.
The code for calculating the length of the LCS could look something like this.
pub fn dynamic_lcslen(x: &Vec<char>, y: &Vec<char>) -> usize {
let m = x.len();
let n = y.len();
let mut matrix = vec![vec![0; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
if x[i - 1] == y[j - 1] {
matrix[i][j] = matrix[i - 1][j - 1] + 1;
} else if matrix[i - 1][j] >= matrix[i][j - 1] {
matrix[i][j] = matrix[i - 1][j];
} else {
matrix[i][j] = matrix[i][j - 1];
}
}
}
matrix[m][n]
}Run the program using the following command.
cargo runExample output is shown below.
$ cargo run
fibonacci(5)
Recursive: 5
Array: 5
Dyanamic: 5
==========
binomial(5, 3)
Recursive: 10
Array: 10
Dyanamic: 10
==========
trinomial(5, 3)
Recursive: 15
Array: 15
Dyanamic: 15
==========
lcslen(TGCGTCCAT, TACGTGCGCT)
Recursive: 7
Dyanamic: 7