exponential time and produce polynomial-time algorithms to solve them dynamic programming is one such technique in additionthe algorithms that result from applications of the dynamic programming technique are usually quite simple-often needing little more than few lines of code to describe some nested loops for filling in table the components of dynamic programming solution the dynamic programming technique is used primarily for optimization problemswhere we wish to find the "bestway of doing something often the number of different ways of doing that "somethingis exponentialso bruteforce search for the best is computationally infeasible for all but the smallest problem sizes we can apply the dynamic programming technique in such situationshoweverif the problem has certain amount of structure that we can exploit this structure involves the following three componentssimple subproblemsthere has to be some way of repeatedly breaking the global optimization problem into subproblems moreoverthere should be simple way of defining subproblems with just few indiceslike ijkand so on subproblem optimizationan optimal solution to the global problem must be composition of optimal subproblem solutions we should not be able to find globally optimal solution that contains suboptimal subproblems subproblem overlapoptimal solutions to unrelated subproblems can contain subproblems in common having given the general components of dynamic programming algorithmwe next show how to apply it to the longest common subsequence problem problem applying dynamic programming to the lcs we can solve the longest common subsequence problem much faster than exponential time using the dynamic programming technique as mentioned aboveone of the key components of the dynamic programming technique is the definition of simple subproblems that satisfy the subproblem optimization and subproblem overlap properties recall that in the lcs problemwe are given two character stringsx and yof length and mrespectivelyand are asked to find longest string that is subsequence of both and since and are character stringswe have natural set of indices with which to define subproblems--indices into the strings and let us define subproblemthereforeas that of computing the value [ij]