Dynamic Programming - C P P

  • Memory
    • Stack
      • Static Memory Allocation
      • FILO
      • Fixed Size
      • Automatic memory allocation and de-allocation at compile-time
    • Heap
      • Dynamic Memory Allocation
      • Not fixed size
      • Takes more memory as compared to stack as pointer is also needed
        • Pointer is stored in stack while other memory is created in Heap
      • Manual memory allocation and de-allocation at run-time
      • new keyword is used, returns address of the memory allocated
        • char* variableName = new char;
        • ptr = NULL => Point it towards no value, Gets destroyed when exiting from stack
      • Array
        • int *variableName = new int[n]; => Creating an 1D array
        • A = new dataType[n] => Initialize an array of size n, A pointer stores the memory address of first element
        • dataType *A = new int[n * m] => Dynamically declare an 2D array
        • Traversing through 3D Array
              for (int i = 0; i < R; i++) {
                  for (int j = 0; j < C; j++) {
                      for (int k = 0; k < D; k++) {
                        cout << *(A + i * C * D + j * D + k);
                      }
                  }
              }
          
        • Creating an 2D array
              int **A = new int *[R];
              for (int i = 0; i < R; i++) {
                  A[i] = new int[C];
              }
              // Initialize the elements
              for (int i = 0; i < R; i++) {
                  for (int j = 0; j < C; j++) {
                      cin >> A[i][j];
                  }
              }
              // Print the elements
              for (int i = 0; i < R; i++) {
                  for (int j = 0; j < C; j++) {
                    cout << *(A + i * R + j);
                  }
                  cout << endl;
              }
              // Deallocate the memory
              for (int i = 0; i < R; i++) {
                  delete[] A[i];
              }
              delete[] A;
          
      • Memory Leak => When you allocates memory and forget to de-allocate
        • delete keyword is used
        • delete variableName;
        • delete[] variableName; => For array deletion
  • Types of Problem
    • Optimal Substructure
      • If we can write a recurrence relation, break into smaller problems
    • Overlapping Subproblem
      • If our sub-problems repeat
      • Solution
        • Memoization/Top-down
          • Lookup table is maintained and checked before any computation
          • Using Recursion, but table is filled bottom-up
        • Tabulation/Bottom-up
          • Solution is built from base
          • Using Iteration
          • Using DP, but table is filled top-down
Share: