DP UGUI_101

nCrSolution.java

public static int[][] table = new int[50][50];

   public static void main(String[] args) {
	// write your code here
    }

    static void init()
    {
        Arrays.fill(table,-1);
    }
    static int nCr(int n, int r)
    {
        if(r==1) return n;
        if (n==r) return 1;
        if (table[n][r] != -1)
        {
            return table[n][r];
        }
        table[n][r] = nCr(n-1,r) +nCr(n-1,r-1);
        return table[n][r];
    }

Problem 1

Problem Statement: On a positive integer, you can perform any one of the following 3 steps. 
1.) Subtract 1 from it. ( n = n - 1 )  , 
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). 
Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1

eg: 
1.)For n = 1 , output: 0       
2.) For n = 4 , output: 2  ( 4  /2 = 2  /2 = 1 )    
3.)  For n = 7 , output: 3  (  7  -1 = 6   /3 = 2   /2 = 1 )

Problem1.java

package com.Shubhra;

public class Memoization
{
    int[] memo = new int[50];// 50 is the max n

    int getMinSteps(int n)
    {
        if (n==1) return 0;
        if (memo[n]!=-1) return memo[n];

        int r = 1 + getMinSteps(n-1);
        if (n%2==0) r = Math.min(r,1+getMinSteps(n/2));
        if (n%3==0) r = Math.min(r,1+getMinSteps(n/3));

        memo[n] = r;
        return r;
    }
}

TODO

When you are done with the LIS, read this blog till the "Intermediate" Category, and try to solve the problems inside "Elementary"
Category

https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/

https://algorithmist.com/wiki/Longest_increasing_subsequence#Dynamic_Programming