Dynamic Programming

Dynamic Programming Problems Time Complexity
Longest Common Subsequence (LCS) O ( M * N ). M and N are the lengths of the first and second sequence respectively.
Longest Increasing Subsequence (LIS) O ( N 2 ). N is the number of elements in the sequence.
Matrix Chain Multiplication O ( N 3 ). N is the number of matrices.
Longest Palindromic Substring O ( N 2 ). N is the length of the string.
Maximum Sum Subarray O ( N ). N is the number of elements in the subarray.
0-1 Knapsack O ( N * M ). N is the capacity of the knapsack and M is the number of weights available for putting into the knapsack.
Coins Change Problem O ( N * M ). N is the bigger coin to be exchanged and M is the number of smaller coins to be used for exchanging
Integer Partitioning Problem O ( N * M ). N is the bigger number to be partitioned and M is the number of smaller integers to be used for partitioning.
Maximum Sum SubRectangle using aggregate rectangles O ( N 4 ). N is the number of elements in the rows / columns in the rectangle.
Maximum Sum SubRectangle using Kadane’s algorithm O ( N 3 ). N is the number of elements in the rows / columns in the rectangle.


Copyright (c) 2019-2023, Algotree.org.
All rights reserved.