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 height when coins are arranged in a triangle

public class MaxHghtToArrangeTri {

    

     /**

      *         *           ß 1 coin

      *   *         *       ß 2 coin

      * *      *          * ß 3 coin

      *

      * Coins need for Height H = 1 + 2 + 3 + ........ + H-1

      *                                 = H(H-1)/2

      * @param coins

      * @return

      */

     private static int getMaxHeight(int coins) {

          

           int d = (int)Math.pow((8*coins + 1),.5);

          

           int height = (d + 1)/2;

          

           return height-1;

     }

    

     /**

      * @param args

      */

     public static void main(String[] args) {

           int coins = 7;

           int maxHeight = getMaxHeight(coins);

          

           System.out.println(maxHeight);

     }

}

Smallest Integer multiplication to floating number which convert it to natural

We need to find the Integer Multiplier to convert a floating number to Natural.

Input : 1.66

Output : 50

Input : 0.25

Output : 4

public class MinMulToMakeNatural {

     /**

      * Get Minimum multiplier to make Natural.

      * @param number

      * @return min mult.

      */

     private static int getMinMultiplier(float number) {

           char[] array = (number+"").toCharArray();

          

           int len = array.length;

           int numerator = array[0]- '0';

           int count = 0;

          

           boolean flag = false;

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

                if('.'==array[i]) {

                     flag= true;

                     continue;

                }

               

                if(flag) {

                     count++;

                }

               

                int val = array[i] - '0';

                numerator = numerator * 10 + val;

           }

          

           int denominator = (int)Math.pow(10,count);

          

           int gcd = getGCD(numerator,denominator);

          

           return denominator/gcd;

     }   

    

     /**

      * @param numerator

      * @param denominator

      * @return GCD

      */

     private static int getGCD(int numerator, int denominator) {

          

           int gcd = denominator==0?numerator:

                getGCD(denominator, numerator%denominator);

          

           return gcd;

     }

     /** Main method. */

     public static void main(String[] args) {

           float number = 1.66F;

          

           int min = getMinMultiplier(number);

          

           System.out.println("Minimum Integer Multiplier# "+min);

     }

}

Program to generate unique CAPTCHA to verify an user

A CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a test to determine whether the user is human or not.

CAPTCHA provides a way to block bots from interacting with your site by providing something that's hard for them to read, but easy for people to read.

import java.util.Random;

public class GenerateCaptcha {

      /**

       * Generate Length between 5 and 8.

       * @return return length.

       */

      private static int generateRandomLength() {

            int length = 5 + Math.abs((random.nextInt()%4));

            return length;

      }

      /**

       *  Generate a CAPTCHA String consisting of random

       *  lower case & upper case letters, and numbers.

       */

      private static String generateCaptchaString(int length) {

           

            StringBuffer captchaBuffer = new StringBuffer();

           

            for (int i = 0; i < length; i++) {

                 

                  /** Generate the Random Character between 0 to 61.

                   * NOTE: Take abs value, because there may

                   * be ArrayIndexOutOfBount

                   * Exception for negative number*/

                  int rndCharIdx = Math.abs(random.nextInt()) % 62;

                 

                  char character = characters[rndCharIdx];

                 

                  captchaBuffer.append(character);

            }

            return captchaBuffer.toString();

      }

      private static Character[] characters = {'a','b','c','d','e','f',

            'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u',

            'v','w','x','y','z','A','B','C','D','E','F','G','H','I','J',

            'K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y',

            'Z','0','1','2','3','4','5','6','7','8','9'};

      private static Random random = new Random();

      public static void main(String[] args) {

            int rndmCaptchaLen = generateRandomLength();

            String captcha = generateCaptchaString(rndmCaptchaLen);

            System.out.println("Random Captcha #"+captcha);

      }

}