Dynamic Programming

What is dynamic programming? Dynamic programming is kind of careful brute force where you try all possibilities but carefully. Before going into the definition, lets first take a problem, so that we can define the dynamic programming. Why was it named this way? Check out the history here. Problem - Nth Fibonacci Number Dynamic programming is a method for efficiently solving a broad range of search and optimization problems which exhibit the characteristics of overlappling subproblems and optimal substructure. [Read More]

m: A B C B D A B yn: B D C A B A The LCS is B C B A For arbitrary inputs, it is NP-hard. For constant inputs, DP gives the solution in polynomial time ex: O(n^k). Also, there can be more than one LCSs and the solution for that is exponential time ex: O(k^n). Here we maintain an LCS matrix of m*n size. Initially, for i= 0 or j = 0, LCSij = 0. [Read More]