Hello Everyone,
Let us discuss the Longest Increasing Subsequence (LIS) problem as an example problem that can be solved using Dynamic Programming.
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
Examples:
Input: arr[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 The longest increasing subsequence is 3, 10, 20 Input: arr[] = {3, 2} Output: Length of LIS = 1 The longest increasing subsequences are {3} and {2} Input: arr[] = {50, 3, 10, 7, 40, 80} Output: Length of LIS = 4 The longest increasing subsequence is {3, 7, 40, 80}
Method : Dynamic Programming.
We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
The simulation of approach will make things clear:
Input : arr[] = {3, 10, 2, 11} LIS[] = {1, 1, 1, 1} (initially)
Iterationwise simulation :
 arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
 arr[3] < arr[1] {No change}
 arr[3] < arr[2] {No change}
 arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
 arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
 arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}
We can avoid recomputation of subproblems by using tabulation as shown in the below code:
Below is the implementation of the above approach:
/* Dynamic Programming C++ implementation
of LIS problem */
#include <bits/stdc++.h>
using
namespace
std;
/* lis() returns the length of the longest
increasing subsequence in arr[] of size n */
int
lis(
int
arr[],
int
n)
{
int
lis[n];
lis[0] = 1;
/* Compute optimized LIS values in
bottom up manner */
for
(
int
i = 1; i < n; i++) {
lis[i] = 1;
for
(
int
j = 0; j < i; j++)
if
(arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
// Return maximum value in lis[]
return
*max_element(lis, lis + n);
}
/* Driver program to test above function */
int
main()
{
int
arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
printf
(
"Length of lis is %d\n"
, lis(arr, n));
return
0;
}
Output
Length of lis is 5
Output:
Length of lis is 5
Complexity Analysis:

Time Complexity: O(n2).
As nested loop is used. 
Auxiliary Space: O(n).
Use of any array to store LIS values at each index.
Note: The time complexity of the above Dynamic Programming (DP) solution is O(n^2) and there is a O(N log N) solution for the LIS problem. We have not discussed the O(N log N) solution here as the purpose of this post is to explain Dynamic Programming with a simple example. See below post for O(N log N) solution.