Dynamic Programming

Dynamic Programming is an algorithmic model that solves a given complex problem by breaking it down into a collection of simpler subproblems and stores the results of subproblems to avoid computing the same results again.

A problem has two below properties can be solved using Dynamic programming.

1) Overlapping subproblems

2) Optimal substructure

1) Overlapping subproblems

If the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems. Computed solutions to subproblems are stored in a table so that these don’t have to recomputed.

So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.

2) Optimal substructure

A problem is said to have optimal substructure if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.

Maximum weight path ending of last row in a matrix

Find the path having the maximum weight in integer matrix [N X M].

Conditions for moves:

Path should begin from top left element and can end at any element of last row. We can move to down (i+1, j) or diagonal forward (i+1, j+1).

public class MaxWeightPathMatrix {

    

     /**

      * Moves # down or forward diagonal.

      * @param matrix

      * @return Returns the maximum weight.

      */

     private static int getMaxWeightPath(int[][] matrix) {

           int row = matrix.length;

           int col = matrix[0].length;

           int[][] dp = newint[row][col];

           /** Initialize first row of total weight */

           for(inti=0;i<col;i++) {

                dp[0][i] = matrix[0][i];

           }

           /** Initialize first column of total weight */

           for (inti=1; i<row; i++) {

                dp[i][0] = matrix[i][0] + dp[i-1][0];

           }

           for(inti=1; i<row; i++) {

                for(intj=1; j<col; j++) {

                     dp[i][j] = matrix[i][j] + Math.max(dp[i-1][j],

                                dp[i-1][j-1]);

                }

           }

           /** Max weight path sum to rech the last row */

           int result = 0;

           for (inti=0; i<col; i++) {

                result = Math.max(dp[row-1][i], result);

           }

           return result;

     }

    

     /** Driver method. */

     public static void main(String[] args) {

          

           int[][] matrix = {{ 8, 4 ,6 ,8 ,2 },

                     { 4 , 18 ,2 ,20 ,10 },

                     {20, 2 ,6 , 0 ,40 },

                     {32 ,184, 82, 88 ,2},

                     {16, 302, 12, 8, 18}};

           int maxWeight = getMaxWeightPath(matrix);

           System.out.println("Maximum weight path ending at any"

                     + " element of last row in a matrix # "+ maxWeight);

     }

}

Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequences don’t have same string character at same position, i.e., any k’th character in the two subsequences shouldn’t have the same index in the original string.

This problem can be solved using the Longest Common Subsequence problem. LRS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.

package amazon.dp;

public classLongestRptSubseq {

     private static int getLRS(String string) {

          

           char[] charArray = string.toCharArray();

           int len = charArray.length;

          

           int[][] dp = new int[len+1][len+1];

          

           for(int i=1;i<=len;i++) {

               

                for (int j=1;j<=len;j++) {

                     // If characters match and indexes are not same

                     if (charArray[i-1] == charArray[j-1] && i!=j) {

                           dp[i][j] =  1 + dp[i-1][j-1];

                          

                     } else {

                           // If characters do not match

                           dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

                     }

                }

           }

          

           return dp[len-1][len-1];

     }

     public static voidmain(String[] args) {

           String string = "amazonazom";

           int len = getLRS(string);

           System.out.println("Longest Repeating Subsequence "+len);

     }

}

Count number of ways to cover a distance

Count total number of ways to cover the distance with 1, 2 and 3 steps.

Recursion solution time complexity is exponential i.e. O(3n).

Since same sub problems are solved again, this problem has overlapping sub problems property. So min square sum problem has both properties of a dynamic programming problem.

public class MaxStepsCount {

     /** Dynamic Programming. */

     private static int getMaxWaysDP(int distance) {

           int[] count = new int[distance+1];

           count[0] = 1;

           count[1] = 1;

           count[2] = 2;

           /** Memorize the Sub-problem in bottom up manner*/

           for (int i=3; i<=distance; i++) {

                count[i] = count[i-1] + count[i-2] + count[i-3];               

           }

           return count[distance];

     }

     /** Recursion Approach. */

     private static int getMaxWaysRecur(intdistance) {

           if(distance<0) {

                return 0;

           } else if(distance==0) {

                return 1;

           }

           return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)

                     +getMaxWaysRecur(distance-3);

     }

     public static void main(String[] args) {

           // Steps pf 1, 2 and 3.

           int distance = 10;

           /** Recursion Approach. */

           int ways = getMaxWaysRecur(distance);

           System.out.println(ways);

           /** Dynamic Programming. */

           ways = getMaxWaysDP(distance);

           System.out.println(ways);

     }

}