Very Basic Java Programs

[1] Count ways to reach a score using 1 and 2 with no consecutive 2s
A cricket player has to score N runs, with condition he can take either 1 or 2 runs only and consecutive runs should not be 2. Find all the possible combination he can take.
Examples:

Input : N = 4
Output : 4
1+1+1+1, 1+2+1, 2+1+1, 1+1+2

Input : N = 5
Output : 6

This problem is a variation of count number of ways to reach given score in a game and can be solved in O(n) time and O(n) auxiliary space.

Below is the recursive solution of above problem.

// A simple recursive implementation for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
 
import java.io.*;
 
class GFG {
   static  int CountWays(int n, boolean flag)
{
    if (n == 0) // base case
        return 1;
 
    int sum = 0;
 
    // 2 is not scored last time so we can score either 2 or 1
    if (flag == false && n > 1)
        sum = sum + CountWays(n - 1, false) + CountWays(n - 2, true);
 
    // 2 is scored last time so we can only score 1
    else
        sum = sum + CountWays(n - 1, false);
 
    return sum;
}
    // Driver code
    public static void main (String[] args) {
            int n = 5;
            System.out.println(CountWays(n, false));
    }
}

Output:
6
This problem has optimal substructure property as the problem can be solved using solutions to subproblems.
Below is the Dp solution of above problem

import java.util.Arrays;
 
// A memoization based implementation for
// counting ways to reach a score using 
// 1 and 2 with consecutive 2 allowed
class GfG 
{
 
    static int MAX = 101;
    static int dp[][] = new int[MAX][2];
 
    static int CountWays(int n, int flag) 
    {
        // if this state is already visited return
        // its value
        if (dp[n][flag] != -1) 
        {
            return dp[n][flag];
        }
 
        // base case
        if (n == 0)
        {
            return 1;
        }
 
        // 2 is not scored last time so we can
        // score either 2 or 1
        int sum = 0;
        if (flag == 0 && n > 1) 
        {
            sum = sum + CountWays(n - 1, 0) +
                    CountWays(n - 2, 1);
        } 
         
        // 2 is scored last time so we can only score 1
        else
        {
            sum = sum + CountWays(n - 1, 0);
        }
 
        return dp[n][flag] = sum;
    }
 
    public static void main(String[] args) 
    {
        int n = 5;
        for (int i = 0; i < MAX; i++) 
        {
            Arrays.fill(dp[i], -1);
        }
        System.out.println(CountWays(n, 0));
    }
}
 
/* This code contributed by PrinciRaj1992 */
Output:
6