Memoization and Dynamic programming

10 July 2023

As usual, today was completely dedicated to DSA more specifically Dynamic Programming. Today I solved 5 Leetcode questions

What did I learn?

We use techniques like memoization and dynamic programming to decrease the time complexity.

Fibonacci Number

My approach:

Until today the solution I knew was correct but had exponential time complexity which is very bad but then today I learned about Memoization and Dynamic programming to decrease time complexity by storing the results and using them whenever it is required. The time complexity after optimization is O(n).

My solution:
- Brute Force
  
```cpp class Solution { public:

int fib(int n) { if(n<=1){ return n; }

int a = fib(n-1); int b = fib(n-2);

return a+b; } };


        * Memoization

            ```cpp
            class Solution {
            public:

                int helper(int n, int* arr){
                    if(n<=1){
                        return n;
                    }

                    if(arr[n]!=-1){
                        return arr[n];
                    }

                    int a = helper(n-1,arr);
                    int b = helper(n-2,arr);

                    arr[n] = a+b;

                    return arr[n];
                }

                int fib(int n) {

                    int arr[n+1];

                    for(int i=0;i<=n;i++){
                        arr[i] = -1;
                    }
                    return helper(n,arr);
                }
            };

Dynamic Programming

  class Solution {
  public:

      int fib(int n) {
          if(n<=1){
              return n;
          }

          int arr[n+1];

          arr[0] = 0;
          arr[1] = 1;

          for(int i=2;i<=n;i++){
              arr[i] = arr[i-1]+arr[i-2];
          }

          return arr[n];
      }
  };

Climbing Stairs

My approach:

This question is very similar to the Fibonacci question so I do know the brute force solution but I chose to directly solve it by using memoization and dynamic programming. The time complexity of the solution is O(n).

My solution:

Memoization

  class Solution {
  public:
      int helper(int n, int* arr){
          if( n==0){
              return 1;
          }
          if(n<=2){
              return n;
          }

          if(arr[n]!=-1){
              return arr[n];
          }

          int a = helper(n-1,arr);
          int b = helper(n-2,arr);
          arr[n] = a+b;
          return arr[n];
      }

      int climbStairs(int n) {
          int arr[n+1];

          for(int i=0;i<=n;i++){
              arr[i] = -1;
          }

          int output = helper(n,arr);
          return output;
      }
  };

Dynamic Programming

  class Solution {
  public:

      int climbStairs(int n) {
          if(n==0){
              return 1;
          }
          if(n<=2){
              return n;
          }

          int arr[n+1];
          arr[0] = 0;
          arr[1] = 1;
          arr[2] = 2;

          for(int i=3;i<=n;i++){
              arr[i] = arr[i-1]+arr[i-2];
          }

          return arr[n];
      }
  };

Minimum Depth of Binary Tree

My approach:

I was able to do this question using recursion in the O(n) time.

My solution:

 class Solution {
 public:
     int minDepth(TreeNode* root) {
         if(root==NULL){
             return 0;
         }

         if(root->left==NULL && root->right==NULL){
             return 1;
         }

         int ans1 = minDepth(root->left);
         int ans2 = minDepth(root->right);

         if(ans1==0 || ans2==0){
             return max(ans1,ans2)+1;
         }
         return min(ans1,ans2)+1;
     }
 };

Add Digits

My approach:

The question wasn't complicated but it was asked if we could solve it using constant time. I was able to come up with the O(logn) solution and for O(1) solution I referred to solutions and I realized how you can use patterns if the output space is small and constant. In this, the answer will lie between 1 to 9 so we could find some pattern and come up with the solution in constant time.

My solution:

Brute force [O(n)]

  class Solution {
  public:
      int addDigits(int num) {

          if(num<10){
              return num;
          }
          int output = 0;

          while(num>=0){
              if(num==0){
                  if(output<10){
                      return output;
                  }
                  num = output;
                  output=0;   
              }else{
                  int rem = num%10;
                  num = num/10;
                  output +=rem;
              }
          }
          return output;
      }
  };

Optimized [O(1)]

  class Solution {
  public:
      int addDigits(int num) {

          return 1+(num-1)%9;

      }
  };

Ugly Number

My approach:

I used recursion to solve this question. However, it could be done using loops as well. The time complexity of my solution is O(n).

My solution:

 class Solution {
 public:

     bool helper(int n, int* arr){
         if(n==2 || n==3 || n==5){
             return true;
         }

         for(int i=0;i<3;i++){
             if(n%arr[i]==0){
                 return helper(n/arr[i], arr);
             }
         }
         return false;
     }

     bool isUgly(int n) {
         if(n<=0){
             return false;
         }
         if(n==1){
             return true;
         }
         int arr[] = {2,3,5};
         bool output = helper(n,arr);
         return output;

     }
 };

Day 11 (30 Days of Code)

10 July 2023

What did I learn?