public class RatMaze {
public static void main(String[] args) {
int[][] maze = {
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 }
};
int m = maze.length;
int n = maze[0].length;
int[][] solution = new int[m][n];
boolean isSolutionAvailable = getSolution(maze, solution, 0, 0);
if (isSolutionAvailable) {
printMatrix(solution);
} else {
System.out.println("Solution is not available");
}
}
private static void printMatrix(int[][] a) {
System.out.println();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
System.out.print(" " + a[i][j] + " ");
}
System.out.println();
}
}
private static boolean getSolution(int[][] maze, int[][] solution, int i,
int j) {
int m = maze.length;
int n = maze[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || maze[i][j] == 0) {//check if path is blocked
return false;
}
if (i == m - 1 && j == n - 1) {
solution[i][j] = 1;
return true;
}
// At each position look in forward and downward direction.
if (getSolution(maze, solution, i, j + 1)
|| getSolution(maze, solution, i + 1, j)) {
solution[i][j] = 1;
return true;
}
return false;
}
}
public class MinNumberOfJumps {
private static int MAX = 23234;
public static void main(String[] args) {
int[] jumps = { 2, 3, 1, 1, 4 };
int minJumps = getMinJumps(jumps, jumps.length);
if (minJumps < MAX)
System.out
.println("Minimum number of jumps needed to reach the end of the array is : "
+ minJumps);
else
System.out.println("Cannot reach the end position of the array");
}
private static int getMinJumps(int[] jumps, int size) {
//Boundry conditions
if (jumps == null || size == 0 || jumps[0] == 0)
return MAX;
int[] dp = new int[size];
//Initialization of dp[i]
for (int i = 0; i < size; i++)
dp[i] = MAX;
dp[0] = 0;//no need to jump at first element
for (int i = 1; i < size; i++) {
for (int j = 0; j <= i; j++) {
if (jumps[j] >= (i - j)) {//check if jump is possible from j to is
if (dp[j] + 1 < dp[i]) //check if better solution available
dp[i] = dp[j] + 1;
}
}
}
return dp[size - 1];
}
}
public class AppleProblem {
public static void main(String[] args) {
int[][] apples = { { 2, 3, 1 }, { 4, 6, 2 }, { 7, 8, 2 } };
int rows = apples.length;
int columns = apples[0].length;
// Create a temporary array to store the maximum sum upto that position
int[][] dp = new int[rows][columns];
int prevRowValue = 0;
int prevColumnValue = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (i - 1 < 0)
prevRowValue = 0;
else
prevRowValue = dp[i - 1][j];
if (j - 1 < 0)
prevColumnValue = 0;
else
prevColumnValue = dp[i][j - 1];
dp[i][j] = apples[i][j] + max(prevRowValue, prevColumnValue);
}
}
System.out.println(dp[rows - 1][columns - 1]);
}
private static int max(int a, int b) {
return a > b ? a : b;
}
}
public class CharCombinationWithNumbers {
private static char[] alphabet = "abcdefghijklmnopqrstyuvxyz".toCharArray();
public static void main(String[] args) {
printPossibilities("", "1234");
}
private static void printPossibilities(String partialString, String string) {
if (string == null || string.length() < 1) {
System.out.println(partialString);
return;
}
int digit = Integer.parseInt(string.substring(0, 1));
printPossibilities(partialString + alphabet[digit], string.substring(1));
if (string.length() > 1) {
digit = Integer.parseInt(string.substring(0, 2));
if (digit >= 10 && digit < alphabet.length) {
printPossibilities(partialString + alphabet[digit], string
.substring(2));
}
}
}
}
public class KnapSack {
private static final int MIN = 232345;
public static void main(String[] args) {
int[] v = { 34, 12 };
int amount = 2;
int coins = getMinimumNumberOfCoins(v, amount);
if (coins < MIN) {
System.out.println("Coins required are : " + coins);
} else {
System.out
.println("Cannot give denominations for the given amount");
}
int[] dp = new int[amount + 1];
for (int i = 0; i <= amount; i++) {
dp[i] = MIN;
}
coins = getMinimumNoOfCoinsDp_Recursion(v, amount, dp);
if (coins < MIN) {
System.out.println("DP : Coins required are : " + coins);
} else {
System.out
.println("DP : Cannot give denominations for the given amount");
}
}
private static int getMinimumNumberOfCoins(int[] v, int amount) {
int minimum = MIN;
if (amount == 0)
minimum = 0;
else if (amount > 0) {
for (int i = 0; i < v.length; i++) {
int temp = 1 + getMinimumNumberOfCoins(v, amount - v[i]);
if (temp < minimum)
minimum = temp;
}
}
return minimum;
}
// Dp with recursion
private static int getMinimumNoOfCoinsDp_Recursion(int[] v, int amount,
int[] dp) {
if (amount < 0)
return MIN;
if (dp[amount] < MIN)
return dp[amount];
int minimum = MIN;
dp[0] = 0;
if (amount == 0)
minimum = 0;
else if (amount > 0) {
for (int i = 0; i < v.length; i++) {
int temp = 1 + getMinimumNoOfCoinsDp_Recursion(v,
amount - v[i], dp);
if (temp < minimum)
minimum = temp;
}
}
return dp[amount] = minimum;
}
}
public class KnapSack {
private static final int MIN = 232345;
public static void main(String[] args) {
int[] v = { 34, 12 };
int amount = 2;
int coins = getMinimumNumberOfCoins_DP(v, amount);
if (coins < MIN) {
System.out.println("Coins required are : " + coins);
} else {
System.out
.println("Cannot give denominations for the given amount");
}
}
private static int getMinimumNumberOfCoins_DP(int[] v, int amount) {
if (amount <= 0)
System.out.println("Amount is zero");
int[] min = new int[amount + 1];
min[0] = 0;
for (int i = 1; i <= amount; i++)
min[i] = MIN;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < v.length; j++) {
if (v[j] <= i && min[i - v[j]] + 1 < min[i])
min[i] = min[i - v[j]] + 1;
}
}
return min[amount];
}
}
public class MaxNonConsecutiveSum {
public static void main(String[] args) {
int[] a = { 6, 4, 2, 8, 1 };
System.out.println(getMaxNonConsecutiveSum(a, 0));
System.out.println(getMaxNonConsecutiveSumDp(a));
}
private static int getMaxNonConsecutiveSum(int[] a, int pos) {
if (pos >= a.length)
return 0;
// If we include element at position 'i', we should not include position
// 'i+1'.So we start from 'i+2'
// if we don't select position 'i', then we start recurrence from i+1
return max(a[pos] + getMaxNonConsecutiveSum(a, pos + 2),
getMaxNonConsecutiveSum(a, pos + 1));
}
private static int max(int a, int b) {
return a > b ? a : b;
}
private static int getMaxNonConsecutiveSumDp(int[] a) {
if (a.length == 0)
return 0;
if (a.length == 1)
return a[0];
// create a temporary array to hold max non consecutive sums as sub
// problems'
int[] dp = new int[a.length];
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for (int i = 2; i < a.length; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
}
return dp[a.length - 1];
}
}
package arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Input: 2
* 3
* 1
* 2 1
* 1 2 3
*
* 4
* 1
* 1 2
* 4 1 2
* 2 3 1 1
*
* Output: 5
* 9
*
* @author rajeevprasanna
*
*/
public class MaxDownwardSum {
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine());
int n, i, j;
int[][] a = new int[100][100];
while (t-- > 0) {
n = Integer.parseInt(in.readLine());
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
a[i][j] = Integer.parseInt(in.readLine());
}
}
for (i = n - 2; i >= 0; i--) {
for (j = 0; j <= i; j++) {
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
}
System.out.println(a[0][0]);
}
}
private static int max(int a, int b) {
return a > b ? a : b;
}
}
