Dynamic Programming

Dynamic programming is solving problems by breaking them into overlapping subproblems and storing their results to avoid recomputation.

Types of Dynamic Programming

There are two main ways of solving dynamic problems, top-down and bottom-up.

Top-down Approach (Memoization)

In this method, the solution starts from the highest value n and the function is defined such that it can be called recursively. To account for large arrays, the computations for all indices are stored in a hash map to avoid calculating them again.

I previously used this approach for climbing stairs problem without realising it. The solution with top-down approach is as follows:

#include <unordered_map>
using namespace std;
 
class Solution {
public:
  unordered_map<int, int> createHash() {
    unordered_map<int, int> hashMap;
    hashMap[1] = 1;
    hashMap[2] = 2;
    return hashMap;
  }
  unordered_map<int, int> hashMap = createHash();
  int climbStairs(int n) {
    if (hashMap.count(n))
      return hashMap[n];
    hashMap[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return hashMap[n];
  }
};

Bottom-up Approach (Tabulation)

In this approach, the solution is solved in a loop from smallest to biggest index. The required variables for every steps are stored in variables. This approach should be used wherever possible as it reduces the memory complexity as only the required variables are stored.

The solution to the climbing stairs problem with this approach will be:

#include <unordered_map>
using namespace std;
 
class Solution {
public:
  int climbStairs(int n) {
      if (n==1)
          return 1;
      if (n==2)
          return 2;
      int one = 1;
      int two = 2;
      int ways = 0;
      for(int i=3; i<=n; ++i){
        ways = one + two;
        one = two;
        two = ways;
      }
      return ways;
  }
};