Dynamic Programming: Real-Life Scenarios

Through this, life is much easier to understand.

5 min readNov 25, 2023

Dynamic programming is an optimization technique where a problem is solved by breaking it down into smaller overlapping subproblems. The solutions to subproblems are stored to avoid redundant computations. In this article, I will give you Dynamic Programming examples through Fibonacci sequence and Longest Common Subsequence (LCS).

Solution 1: Fibonacci Sequence

The Fibonacci sequence, while seemingly abstract, has real-life applications, especially in nature, finance, and optimization problems.

class Fibonacci
  def initialize
    @memo = {}
  end

  def fibonacci(n)
    return n if n <= 1

    @memo[n] ||= fibonacci(n - 1) + fibonacci(n - 2)
  end
end

# Example usage
fibonacci_calculator = Fibonacci.new
result = fibonacci_calculator.fibonacci(5)
puts "Fibonacci(5) is #{result}"

Here’s an example of how the Fibonacci sequence is observed in a real-life scenario in the case of Rabbit Population Growth.

Case: Rabbit Population Growth

One classic example of the Fibonacci sequence in a real-life context is modeling the population growth of rabbits. Assume you have a pair of rabbits, one male, and one female, and they produce a new pair of rabbits every month. The new pair becomes mature and starts reproducing from the second month onwards.

The number of rabbit pairs in each month follows the Fibonacci sequence. The sequence represents the number of pairs of rabbits after each month:

Month 1: 1 pair (the initial pair)
Month 2: 1 pair (still only the initial pair is mature)
Month 3: 2 pairs (the initial pair reproduces)
Month 4: 3 pairs (the initial pair reproduces, and the first offspring pair becomes mature)
Month 5: 5 pairs (both the initial and the first offspring pairs reproduce)
Month 6: 8 pairs (the first offspring pair reproduces, and the second offspring pair becomes mature) … and so on.

This population growth pattern can be modeled using the Fibonacci sequence.

Mathematical Representation:

If F(n) represents the number of rabbit pairs after n months, and F(1)=1 and F(2) =1, then

F(n)=F(n−1)+F(n−2).

Ruby Implementation:

def rabbit_population(n)
  return n if n <= 2

  prev, current = 1, 1
  (3..n).each do
    prev, current = current, prev + current
  end

  current
end

# Example usage
months = 6
population = rabbit_population(months)
puts "After #{months} months, there are #{population} pairs of rabbits."

In this example, the rabbit_population method calculates the number of rabbit pairs after a given number of months using the Fibonacci sequence.

This example illustrates how the Fibonacci sequence can be applied to model natural growth phenomena, which is a common occurrence in various biological and ecological systems.

Solution 2: Longest Common Subsequence (LCS)

The next solution to solve Dynamic Programming is through The LCS problems. It involves finding the longest subsequence that two sequences have in common. Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.

class LongestCommonSubsequence
  def lcs(x, y)
    m = x.length
    n = y.length

    # Create a 2D array to store the lengths of LCS for subproblems
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    # Build the DP table in a bottom-up manner
    (1..m).each do |i|
      (1..n).each do |j|
        if x[i - 1] == y[j - 1]
          dp[i][j] = dp[i - 1][j - 1] + 1
        else
          dp[i][j] = [dp[i - 1][j], dp[i][j - 1]].max
        end
      end
    end

    # The length of LCS is stored in the bottom-right cell
    dp[m][n]
  end
end

# Example usage
lcs_calculator = LongestCommonSubsequence.new
sequence1 = "ABCBDAB"
sequence2 = "BDCAB"
length_of_lcs = lcs_calculator.lcs(sequence1, sequence2)
puts "Length of Longest Common Subsequence: #{length_of_lcs}"

In this example, the lcs method of the LongestCommonSubsequence class calculates the length of the Longest Common Subsequence using dynamic programming. The DP table is filled iteratively, considering the characters of both sequences.

Benefits:

Optimization: The dynamic programming approach optimally solves the problem by avoiding redundant calculations, making it more efficient than a naive recursive approach.
Versatility: The LCS problem has applications in various fields, including bioinformatics, text comparison, and version control.

Considerations:

Space Complexity: While the time complexity is efficient, the space complexity of dynamic programming solutions can sometimes be a concern. In this example, the space complexity is O(m * n), where m and n are the lengths of the input sequences.
Adaptability: Dynamic programming can be applied to a wide range of problems, but the specific approach may vary depending on the problem’s nature.

Case: Version Control Systems

In the context of version control systems utilized in software development, the Longest Common Subsequence (LCS) algorithm serves a pivotal role in identifying and managing changes between different versions of source code files. When developers modify a codebase, version control systems, such as Git, leverage the LCS algorithm to discern the longest common subsequence of lines or characters shared between the previous and current versions of a file.

The practical application of the LCS algorithm unfolds when comparing two versions of a file to determine what changes have occurred. In this scenario, each line of code within a file is treated as a sequence of characters. The LCS algorithm efficiently identifies the longest common subsequence of lines between the old and new versions. This information is instrumental in elucidating the unchanged portions of the file, while the differences denote modifications or additions.

In a typical version control workflow, the LCS algorithm aids in minimizing the amount of data that needs to be stored or transmitted, thus optimizing the tracking of changes between versions. This not only enhances efficiency but also facilitates conflict resolution when multiple contributors make alterations to the same file. The LCS algorithm contributes to the clarity of history tracking within version control systems, allowing developers to navigate the evolution of the codebase, revert changes, and comprehend the sequence of modifications over time. Overall, the LCS algorithm in version control systems plays a crucial role in ensuring effective collaboration and management of source code modifications in a software development environment.

Ruby Implementation

def find_changes(old_version, new_version)
  old_lines = old_version.lines.map(&:chomp)
  new_lines = new_version.lines.map(&:chomp)

  lcs_matrix = Array.new(old_lines.length + 1) { Array.new(new_lines.length + 1, 0) }

  (1..old_lines.length).each do |i|
    (1..new_lines.length).each do |j|
      if old_lines[i - 1] == new_lines[j - 1]
        lcs_matrix[i][j] = lcs_matrix[i - 1][j - 1] + 1
      else
        lcs_matrix[i][j] = [lcs_matrix[i - 1][j], lcs_matrix[i][j - 1]].max
      end
    end
  end

  lcs_length = lcs_matrix[old_lines.length][new_lines.length]
  lcs_length
end

# Example usage
old_version = "ABCBDAB"
new_version = "BDCAB"
lcs_length = find_changes(old_version, new_version)
puts "Length of Longest Common Subsequence: #{lcs_length}"

In this Ruby implementation, the find_changes method takes two versions of a file (provided as strings), splits them into lines, and then constructs and fills the LCS matrix. The result is the length of the Longest Common Subsequence.

Keep in mind that this implementation finds the length of the LCS, but you can extend it to actually find the LCS itself if needed. Additionally, in a version control scenario, the LCS information can be used for more advanced tasks, such as generating a side-by-side difference view or applying a three-way merge.