N Queen problem in java

	public static boolean placeQueens(int[][] board, int row, int n)
	{
		if(row >= n) return true;
		
		for(int c = 0; c < n; c++)
		{
			if(isValidPlace(board, row, c, n))
			{
                                 /* Place this queen in board[i][col] */
				board[row][c] = 1;
				
                                // recur for each row
				if(placeQueens(board, row+1, n))
					return true;

				 /* If placing queen in board[i][col] doesn't lead to a solution
                                    then remove queen from board[i][col] */
				board[row][c] = 0; //Backtracking
			}
			
		}
		
		return false;
	}
	
	
	private static boolean isValidPlace(int[][] board, int row, int col, int n)
	{
		
		for(int r = row; r>=0; r--)
			if(board[r][col] == 1) return false;
		
		for(int r=row, c=col; r>=0 && c>=0; r--,c--)
		{
			if(board[r][c] == 1) return false;
		}
		
		for(int r = row, c=col; r>=0 && c < n; r--, c++)
		{
			if(board[r][c] == 1) return false;
		}
		
		return true;
	}

	public static void main(String args[])
	{
		
		int[][] board = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
		
		int n = board.length;

                        if(placeQueens(board, c, n))
			{
				for(int i=0; i < n; i++)
				{
					for(int j=0; j < n; j++)
						System.out.print(board[i][j]+" ");
					System.out.println();
				}
			}else
				System.out.println("Solution does not exist.");
         }

Edit distance of two strings

// Recurssive Function (Min Edit distance of two strings)

 public static int editDistance(String s1, String s2)
 {
  int len1 = s1.length();
  int len2 = s2.length();
  
  return editDistanceUtil(s1,s2,len1-1,len2-1);
 }
 
 private static int editDistanceUtil(String s1, String s2, int i, int j)
 {
  if(i == -1 && j == -1) return 0;
  if(i == -1) return j+1;
  if(j == -1) return i+1;
  int diff = 1;
  if(s1.charAt(i) == s2.charAt(j))
   diff = 0;
  
  return min((editDistanceUtil(s1, s2, i, j-1)+1), 
     (editDistanceUtil(s1, s2, i-1, j-1) + diff), 
     (editDistanceUtil(s1, s2, i-1, j) + 1));
 }
 

Coin changing problem + java

// Minimum no. of coins 


// Recursive solution 

 public static int minCoins(int[] coins, int amount)
 {
  if(amount == 0) return 0;
  
  int min = amount; // max coins can equal to amount
  
  for(int i = 0; i < coins.length; i++)
  {
   if(amount - coins[i] >= 0)
   {
    int noOfCoins = minCoins(coins, amount-coins[i]) + 1;
    
    if(noOfCoins < min)
     min = noOfCoins;
   }
  }
  return min;
 }
 

// Recursion + Extra memory

 public static int minCoinsWithBuf(int[] coins, int amount, int[] buf)
 {
  if(amount == 0)
   buf[amount] = 0;
   
  if(buf[amount] != 0) 
   return buf[amount];
  
  
  int min = amount; // max coins can equal to amount
  
  for(int i = 0; i < coins.length; i++)
  {
   if(amount - coins[i] >= 0)
   {
    int noOfCoins = minCoinsWithBuf(coins, amount-coins[i], buf) + 1;
    
    if(noOfCoins < min)
     min = noOfCoins;
   }
  }
  
  buf[amount] = min;
  
  return buf[amount];
 }
 

// DP / Without Recursion + Extra memory
 
 public static int minCoinsDP(int[] coins, int amount, int[] buf)
 {
  if(amount == 0) return 0;
  
  if(amount == 1) return 1;
  
  buf[0] = 0; buf[1] = 1;
  for(int i = 2; i <= amount; i++)
  {
   int min = amount;
   for(int j = 0; j< coins.length; j++)
   {
    if((i-coins[j] >= 0))
    {
     int c = buf[i-coins[j]]+1;
     if(c < min)
      min = c;
    }
   }
   buf[i] = min;
  }
  return buf[amount];
 }
 


// Main method

 public static void main(String args[])
 {
  int amount = 40;
  int[] coins = {1,3,5,7};
  int[] buf1 = new int[amount+1];
  int[] buf2 = new int[amount+1];
  
  
  
  long time = System.nanoTime();
  System.out.println(minCoins(coins, amount));
  System.out.println("Time1: "+(System.nanoTime() - time));
  
  long time2 = System.nanoTime();
  System.out.println(minCoinsWithBuf(coins, amount, buf2));
  System.out.println("Time2: "+(System.nanoTime() - time2));
  
  
  long time3 = System.nanoTime();
  System.out.println(minCoinsDP(coins, amount, buf1));
  System.out.println("Time3: "+(System.nanoTime() - time3)); 
  
       }

Find maximum number of coins that can be collected in give coins matrix and i can move either right or down from cell.

// Maximum no. of coins 

// int[][] in= {{5,2,8},{10,6,12},{11,5,3}};

// output 36

 public static int maxAmount(int[][] in)
 {
  int row = in.length;
  int col = in[0].length;
  
  //int[][] buf = new int[row][col];
  
  return maxAmountRecUtil(in, row-1, col-1);
  
  //return maxAmountUtil(in, buf, row-1, col-1);
 }
 


// Recursive solution

 private static int maxAmountRecUtil(int[][] in, int i, int j)
 {
  if(i<0 || j<0) return -1;
  
  if(i == 0 && j == 0) return in[i][j];
  
  if(i == 0) return  maxAmountRecUtil(in, i, j-1) + in[i][j];
  
  if(j == 0) return  maxAmountRecUtil(in, i-1, j) + in[i][j];
  
  return  max(maxAmountRecUtil(in, i-1, j), maxAmountRecUtil(in, i, j-1)) + in[i][j];
  
 }
 

// Recursion + Extra memory 
  
 public static int maxAmountUtil(int[][] in, int[][] buf, int i, int j)
 {
  if(i<0 || j<0) return -1;
  
  if(i == 0 && j == 0) buf[i][j] = in[i][j];
  
  if(buf[i][j] != 0) return buf[i][j];
  
  if(i == 0) buf[i][j] =  maxAmountUtil(in, buf, i, j-1) + in[i][j];
  
  if(j == 0) buf[i][j] =  maxAmountUtil(in, buf, i-1, j) + in[i][j];
  
  buf[i][j] =  max(maxAmountUtil(in, buf, i-1, j), maxAmountUtil(in, buf, i, j-1)) + in[i][j];
  
  return buf[i][j];
 }
 

// Dynamic programming 

 public static int maxAmountDP(int[][] in, int[][] buf, int r, int c)
 {
  if(r == 0 && c == 0) buf[0][0] = in[0][0];
  
  for(int j = 1; j <= c; j++)
   buf[0][j] = in[0][j] + buf[0][j-1];
  
  for(int i = 1; i <= r; i++)
   buf[i][0] = in[i][0] + buf[i-1][0];
  
  for(int i = 1; i<=r; i++)
  {
   for(int j=1; j<= c; j++)
   {
    buf[i][j] = max(buf[i-1][j], buf[i][j-1]) + in[i][j];
   }
  }
  return buf[r][c];
 }
 

 private static int max(int m1, int m2) {
  return (m1>m2)?m1:m2;
 }

// Main method

 public static void main(String args[])
 {

  int[][] arr = {{5,2,8},{10,6,12},{11,5,3}};
  int row = arr.length;
  int col = arr[0].length;
  int[][] buf1 = new int[row][col];
                int[][] buf2 = new int[row][col];
  
  long time = System.nanoTime();
  System.out.println(maxAmount(arr));
  System.out.println("Time1: "+(System.nanoTime() - time));
  
  long time2 = System.nanoTime();
  System.out.println(maxAmountUtil(arr, buf1, row-1, col-1));
  System.out.println("Time2: "+(System.nanoTime() - time2));
  
  
  long time3 = System.nanoTime();
  System.out.println(maxAmountDP(arr, buf2, row-1, col-1));
  System.out.println("Time3: "+(System.nanoTime() - time3));
         }