Akash A. Gajjar - OpenGenus IQ: Learn Algorithms, DL, System Design

Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming【O(M*N)】

Count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down. Brute force approach takes exponential time while dynamic programming takes O(M*N) time complexity

Algorithms

The Coin Change Problem

Given a set of coins S with values { S1, S2, ..., Sm }, find the number of ways of making the change to a certain value N. There is an infinite quantity of coins and the order of the coins doesn't matter. This real life problem can be solved by Dynamic Programming in

Dynamic Programming (DP)

Box stacking Problem

Given a set of n types of 3D rectangular boxes, find the maximum height that can be reached stacking instances of these boxes. This problem can be solved efficiently by using Dynamic programming in O(N^2) time complexity and linear O(N) space complexity.

Dynamic Programming (DP)

0-1 Knapsack Problem (Integral Knapsack)

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Brute force approach will take exponential time while a dynamic programming approach will take linear time.

String Algorithms

Algorithm to find the maximum occurring character in a string

Algorithm Pseudocode Complexity Implementation Applications Reading time: 15 minutes | Coding time: 5 minutes One approach to solve this problem would be to sort the input string and then traverse through the sorted string