Destination Tabulation

Welcome to my post on tabulation, where the destination is learning about tabulation (sorry, no tropical vacation)!

Tabulation

Tabulation is an iterative dynamic programming strategy used to efficiently solve large problems by breaking down the problem into smaller problems. It’s considered a bottom up approach since it solves all of the related subproblems first before building larger values from these and solving the the big problem last.

The results of each solved subproblem is stored in a table of n elements (hence its moniker tabulation, but it’s just a plain old array), with the first element in the table being the smallest subproblem and the last element representing the largest and final answer.

What’s Dynamic Programming?

Dynamic programming (DP) is an algorithmic technique used to efficiently solve an optimization problem by breaking the problem down into smaller subproblems. Efficiency is achieved by avoiding duplication calculations and only solving each subproblem once by storing its result in an additional data structure. Each subsequent subproblem will build on the previous subproblem’s result until you get to the last and final problem. There are two DP strategies: tabulation and memoization.

Keep in mind that utilizing DP does not apply for every problem. It can only be used if the problem has a sense of repetitive subproblems that overlap. It can be tricky at first to spot whether a problem should be solved using DP, but more practice and exposure to problems will get you there.

Leetcode: Climbing Stairs

To illustrate tabulation, I’ll walk through the following Leetcode problem: Climbing Stairs.

You are climbing a stair case. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct
ways can you climb to the top?

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 4
Output: 5
Explanation: There are 5 ways to climb to the top.
1. 1 step + 1 step + 1 step + 1 step
2. 2 steps + 1 step + 1 step
3. 2 steps + 2 steps
4. 1 step + 1 step + 2 steps
5. 1 step + 2 step + 1 step

In thinking about our problem, we know it will be n steps to the top but we need to figure out the distinct ways to reach the top. You can only take 1 step or 2 steps each time.

Reaching the i^th step can be done in one of two ways:

1. Take a single step from (i - 1)^th step

2. Take a step of two from (i - 2)^th step

The total number of ways to reach i^th is equal to the sum of the ways of reaching (i - 1)^th step and ways of reaching (i - 2)^th step.

Set Up Your Table

The first thing you'll want to do is set up your table array based on the size of your input. We can do this two ways:

1. create the array off the bat with n elements and filling all values with 0 (since we know we'll be dealing with integers). Then we'll want to initialize some values in the table that will answer trivially small subproblems and edge cases (usually the first entry in the problem).

const n = 4;
const table = new Array(n).fill(0);
// [0, 0, 0, 0]
table[1] = 1;
table[2] = 2; // with 2 steps, there are 2 ways to climb to the top

1. declare the array with the smallest subproblems already included. I'll go with this method since arrays are dynamic in JavaScript and it'll be a bit less code.

const table = [0, 1, 2]; 
// initialized it to include `n = 2`'s subproblem result or else
// it would throw off the below implementation

The following represents what our initialized table looks like:

i	0	1	2	3	4
table[i]	0	1	2

Iterate Through N to Fill in Remaining Table Values

We'll then want to iterate using a for loop starting at 3 since we've already pre-populated the array to account for the earlier subproblems. We'll want to terminate the loop when i is less than or equal to n (i <= n) since the indexes of the array line up with n, as we took 0 steps into consideration.

In the loop, we'll populate the rest of our table by setting the value at index i to be the sum of the previous two subproblems at index i - 1 and i - 2.

Finally, we can return table[n] since it will be the largest final answer.

const climbingStairs = function(n) {
  const table = [0, 1, 2];

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

console.log(climbingStairs(4)); // 5
console.log(climbingStairs(5)); // 8

Visual representation of getting 4:
table[4 - 1] + table[4 - 2]

i	0	1	2	3	4
table[i]	0	1	2	3	5

Time and Space Complexity

The above method uses O(n) time since it has a loop that runs n - 3 times.

The space complexity above is also O(n) because it stores a full array of the subproblems.

There is a way to optimize on space down to O(1) by not storing the full array. We'll only need to save the last two subproblems to help calculate the next one.

const climbingStairs = function(n) {

  // handling edge cases if n equals 0 or 1
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }

  // create last and secondLast variables with 2 and 1, respectively
  // to handle edge cases
  let secondLast = 1; // 
  let last = 2;

  for (let i = 3; i <= n; i++) {
    // initialize temp variable to store last's current value as
   // we'll be reassigning last to the the sum of last + secondLast
    const temp = last;
    last = last + secondLast;
    secondLast = temp;
  }
  return last;
}

console.log(climbingStairs(5)); // 8

I hope you found this helpful. Next week, I’ll look at memoization, the other dynamic programming strategy that utilizes recursion and a hash map. Until then, happy coding!

Climbing Stairs - Leetcode
What is Dynamic Programming? - Educative.io
Tabulation - App Academy
Dynamic Programming - Wikipedia