Let us discuss 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. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

More 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}

Java Code:-

class test{
public static void main(String[] args){
int[] a={3, 10, 2, 1, 20};
int len=a.length;
int[] temp=new int[len];
for(int i=0;i<len;i++){
int cnt=i,lis_cnt=1;
int current_max=a[i];
while(cnt<len){
if(cnt<len-1 && a[cnt+1]>current_max){
current_max=a[cnt+1];
lis_cnt++;
}
cnt++;
}
temp[i]=lis_cnt;
}
int lis_max=0;
for(int i=0;i<len;i++){
if(lis_max<temp[i])
lis_max=temp[i];
}
System.out.println(lis_max);
}
}