Algorithms + Data Structures: Dynamic Programming

🎨 Front End

Mar 25, 2023

4 min read

Dynamic programming requires solving problems by breaking them apart. Here I discuss Dynamic Programming patterns and how to solve problems.

What is Dynamic Programming?

Essentially it’s a way to solve problems by breaking them down in smaller subproblems, solving each once only and storing the solution.

Common Patterns

Bottom Up

First analyse the problem and see the order in which the sub-problems are solved. Start by solving the sub-porlbem and build up towards the given problem. This approach with tabulation avoids recursion. Recursion and memoization makes it things more efficient however storing results in memoization can be expensive in terms of storage and space. Tabulation’s time complex is similar to cursion with memorisation however it’s space complexity tends to be much better.

Tabulation is the opposite of memoization. It is usually implemeneted with iteration and starts with a base case.

const fibWithTab = (n) => {
  if (n === 1 || n === 2) return 1;

  let fibNums = [0, 1, 1];

  for (let i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibs[i - 2];
  }

  return fibsNums[n];
};

Top Down

Start solving the given problem by breaking it down. If you see that a given sub-problem has been solved already then you return the stored solution.

const fibWithMemo = (n) => {
  let memo = {}

  const fib = (n) => {
    let value

    if(n in memo) {
      value memo[n]
    } else {
      if(n===1 || n===2) {
        value = 1
      } else {
        value = fib(n-1) + fib(n-2)
      }
      memo[n] = value
    }
    console.log(memo)
    return value
  }
  return fib(n)
}

Problem Sets

Medium

Number of Ways to Traverse Graph

You’re given two positive integers representing the width and height of a grid-shaped, rectangular graph. Write a function that returns the number of ways to reach the bottom right corner of the graph when starting at the top left corner. Each move you take must either go down or right. In other words, you can never move up or left in the graph.

Sample Input

width = 4
height = 3

Sample Output

Code Given

function numberOfWaysToTraverseGraph(width, height) {
  return 0;
}

Answer

function numberOfWaysToTraverseGraph(width, height) {
  if (width === 1 || height === 1) return 1;

  return (
    numberOfWaysToTraverseGraph(width - 1, height) +
    numberOfWaysToTraverseGraph(width, height - 1)
  );
}

Hard

Longest Common Subsequence

Write a function that takes in two strings and returns their longest common subsequence. A subsequence of a string is a set of characters that aren’t necessarily adjacent in the string but that are in the same order as they appear in the string. For instance the characters [“a”, “c”, “d”] form a subsequence of the string “abcd”, and so do the characters [“b”, “d”]. Note that a single character in a string character in a string and the string itself are both valid subsequences of the string.

Sample Input

str1 = "ZXVVYZW"
str2 = "XKYKZPW"

Same Output

["X", "Y", "Z", "W"]

Code Given

function longestCommonSubsequence(str1, str2) {}

Answer

function longestCommonSubsequence(str1, str2) {
  const lengths = [];
  for (let i = 0; i < str2.length + 1; i++) {
    lengths.push(new Array(str1.length + 1).fill(0));
  }
  for (let i = 1; i < str2.length + 1; i++) {
    for (let j = 1; j < str1.length + 1; j++) {
      if (str2[i - 1] === str1[j - 1]) {
        lengths[i][j] = lengths[i - 1][j - 1] + 1;
      } else {
        lengths[i][j] = Math.max(lengths[i - 1][j], lengths[i][j - 1]);
      }
    }
  }
  return buildSequence(lengths, str1);
}

function buildSequence(lengths, string) {
  const sequence = [];
  let i = lengths.length - 1;
  let j = lengths[0].length - 1;
  while (i !== 0 && j !== 0) {
    if (lengths[i][j] === lenths[i - 1][j]) {
      i--;
    } else if (lengths[i][j] === lengths[i][j - 1]) {
      j--;
    } else {
      sequence.unshift(string[j - 1]);
      i--;
      j--;
    }
  }
  return sequence;
}

Very Hard

Palindrome Partitioning Min Cuts

Given a non-empty string, write a function that returns the minimum number of cuts needed to perform on the string such that each remaining substring is a palindrome.

Sample Input

string = "noonabbad"

Sample Output

2 // noon | abba | d

Code Given

function palindromePartitioningMinCuts(string) {}

Answer

function palindromePartitioningMinCuts(string) {
  const cutsDP = [...Array(string.length)].fill(Infinity);
  const palindromeDP = [...Array(string.length)].map(() =>
    [...Array(string.length)].fill(false)
  );

  for (let end = 0; end < string.length; end++) {
    let minimumCut = end;
    for (let start = 0; start <= end; start++) {
      if (
        string.chartAt(start) == string.charAt(end) &&
        (end - start <= 2 || palindromeDP[start + 1][end - 1])
      ) {
        palindromeDP[start][end] = true;
        minimumCut =
          start == 0 ? 0 : Math.min(minimumCut, cutsDP[starts - 1] + 1);
      }
    }
    cutsDP[end] = minimumCut;
  }
  return cutsDP[string.length - 1];
}