// Grid Unique Paths-->2-D dp concept(space optimised)

// tc = O(mxn) 

// sc = O(n) --> array

import java.util.*;

class dp {

     public static int f(int m, int n)

     {

        int prev[] = new int[n];

        for(int i=0;i<m;i++)

        {

            int temp[] = new int[n];

            for(int j=0;j<n;j++)

            {

                if(i==0&&j==0) {temp[j] = 1;continue;}

            else

            {

                int up=0;int left=0;

               if(i>0)

               up = prev[j];

                if(j>0)

                left = temp[j - 1];

                temp[j] = up + left;

            }

            }

            prev = temp;

        }

        return prev[n - 1];

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

        System.out.println(f(m,n));

    }

}

// Grid Unique Paths-->2-D dp concept(Tabulation)

// tc = O(mxn) 

// sc = O(mxn) --> extra dp array

import java.util.*;

class dp {

     public static int f(int dp[][], int m, int n)

     {

        for(int i=0;i<m;i++)

        {

            for(int j=0;j<n;j++)

            {

                if(i==0&&j==0) {dp[0][0]=1;continue;}

            else

            {

                int up=0;int left=0;

               if(i>0)

                up = dp[i-1][j];

                if(j>0)

                left = dp[i][j-1];

                dp[i][j] = up+left;

            }

            }

        }

        return dp[m-1][n-1];

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

        int dp[][] = new int[m][n];

        // Initialize the DP array with -1 to indicate uncomputed values

        for (int[] row : dp)

            Arrays.fill(row, -1);

        System.out.println(f(dp,m,n));

    }

}

 

 // Count Grid Unique Paths-->2-D dp concept(Memoization)

// tc = O(mxn) -->at max there will be n*m calls of recursion

// sc = O((n-1)+(m-1)) + O(mxn) --> stack space + extra dp array

import java.util.*;

class dp {

     public static int f(int i , int j, int dp[][])

     {

        if(i==0&&j==0) return 1;

        if(i<0||j<0) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int up = f(i-1,j,dp);

        int left = f(i,j-1,dp);

        return dp[i][j]=up+left;

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

        int dp[][] = new int[m][n];

        // Initialize the DP array with -1 to indicate uncomputed values

        for (int[] row : dp)

            Arrays.fill(row, -1);

        System.out.println(f(m-1,n-1,dp));

    }

}

 // Ninja's Training-->2-D dp concept(Memoization)

// tc = O(nx4x3)

// sc = O(n) + O(nx4) --> stack space + extra dp array

import java.util.*;

class dp {

    // Recursive function to calculate the maximum points for the ninja training

    static int f(int day, int last, int[][] points, int[][] dp) {

        // If the result is already calculated, return it

        if (dp[day][last] != -1) return dp[day][last];

        // Base case: When it's the first day (day == 0)

        if (day == 0) {

            int maxi = 0;

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

                if (i != last)

                    maxi = Math.max(maxi, points[0][i]);

            }

            return dp[day][last] = maxi; // Store and return the result

        }

        int maxi = 0;

        // Loop through the three activities on the current day

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

            if (i != last) {

                // Calculate the points for the current activity and recursively

                // calculate the maximum points for the previous day

                int activity = points[day][i] + f(day - 1, i, points, dp);

                maxi = Math.max(maxi, activity); // Update the maximum points

            }

        }

        return dp[day][last] = maxi; // Store and return the result

    }

    // Function to find the maximum points for ninja training

    static int ninjaTraining(int n, int[][] points) {

        // Initialize a memoization table with -1 values

        int dp[][] = new int[n][4];

        for (int[] row : dp)

            Arrays.fill(row, -1);

        // Start the recursive calculation from the last day (n - 1) with the last activity (3)

        return f(n - 1, 3, points, dp);

    }

    public static void main(String args[]) {

        // Define the points for each activity on each day

        int[][] points = {{10, 40, 70},

                          {20, 50, 80},

                          {30, 60, 90}};

        int n = points.length; // Get the number of days

        System.out.println(ninjaTraining(n, points)); // Calculate and print the maximum points

    }

}

 // Maximum Sum of Non-Adjacent Elements(Memoization)

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int arr[],int dp[])

    {

        if(index==0) return arr[index];

        if(index<0) return 0;

        if(dp[index] !=-1) return dp[index];

        int pick = func(index-2, arr,dp) + arr[index];

        int notpick = func(index-1, arr, dp) + 0;

        return dp[index] = Math.max(pick,notpick);

    }

    public static void main(String[] args) {

         int arr[] = {2,1,4,9};

         int n = 3; // or, n=arr.length

         int dp[] = new int[n+1]; // then n

         Arrays.fill(dp,-1);

         System.out.println(func(n,arr,dp));

    }

}

// Frog Jump via Bottom-up(Tabulation)

// tc = O(n)

// sc = O(n) --> extra dp array

import java.util.*;

public class dp {

     

    public static void main(String[] args) {

        int height[]={30,10,60,10,60,50};

        int n = 5; // or when --> n = height.length

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1);

        dp[0] = 0;

        for(int i = 1;i<n+1;i++)

        {

            int left_jmpOne = dp[i-1] + Math.abs(height[i] - height[i-1]);

            int right_jmpTwo = Integer.MAX_VALUE;

            if(i>1){

            right_jmpTwo = dp[i-2] + Math.abs(height[i] - height[i-2]);

             }

            dp[i] = Math.min(left_jmpOne,right_jmpTwo);

        }

        System.out.println(dp[n]); // then n-1

    }

}

// Frog Jump via Memoization

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int height[], int dp[]) {

        if(index==0) return 0;

        if(dp[index] != -1) return dp[index];

        int left_jmpOne = func(index-1,height,dp) + Math.abs(height[index] - height[index-1]);

        int right_jmpTwo = Integer.MAX_VALUE;

        if(index>1)

        {

            right_jmpTwo = func(index-2,height,dp) + Math.abs(height[index] - height[index-2]);

        }

        return dp[index] = Math.min(left_jmpOne,right_jmpTwo);

    }

    public static void main(String[] args) {

        int height[]={30,10,60,10,60,50};

        int n = 5; // n = height.length

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1);

        System.out.println(func(n,height,dp)); // then n-1 here

    }

}

 

// Climbing Stairs | How to Write 1D Recurrence Relations

// tc = O(n)

// sc = O(n) --> stack space

import java.util.*;

public class dp {

    public static int func(int index) {

        if (index == 0) return 1;

        if (index == 1) return 1;

        int left = func(index - 1);

        int right = func(index - 2);

        return left + right;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of stairs: ");

        int n = scanner.nextInt();

        int ways = func(n);

        System.out.println("Number of ways to climb " + n + " stairs: " + ways);

    }

}

 

// Program to convert recursive fibonacci into dp by tabulation method(bottom-up)

// tc= O(n)

// sc= O(1) = extra array space is also removed

import java.util.*;

public class dp {

    public static void main(String[] args) {

       int n = 5;

       //int dp[] = new int[n+1];

       int prev2 = 0;

       int prev = 1;

       System.out.println(prev2);

       System.out.println(prev);

       for(int i = 2; i<n+1;i++)

       {

         int curr = prev + prev2;

         System.out.println(curr);

         prev2 = prev;

         prev = curr;

       }

       //System.out.println(prev);

    }

}

// Program to convert recursive fibonacci into dp

// tc= O(n)

// sc= O(n) + O(n) = stack space + extra array space respectively

import java.util.*;

public class dp {

    public static int func(int n, int[] dp)

    {

         if(n<=1) return n; //base case

         if(dp[n] != -1) return dp[n]; //memoization

         return dp[n]= func(n-1,dp) + func(n-2,dp); //compute

    }

    public static void main(String[] args) {

        int n = 5;

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1); // initialise all with -1

        for (int i : dp) {

            System.out.print(i+" "); // output is -1,-1,-1,-1,-1,-1

        }

        System.out.println();

        System.out.println("----");

        System.out.println(func(n,dp)); // output is 5

        System.out.println("----");

         for (int i : dp) {

            System.out.print(i+" "); // output is: -1,-1,1,2,3,5

        }

    }

}

// Program to convert recursive fibonacci into dp by tabulation method(bottom-up)

// tc= O(n)

// sc= O(n) = extra array space respectively (stack space is removed)

import java.util.*;

public class dp {

    public static void main(String[] args) {

       int n = 5;

       int dp[] = new int[n+1];

       dp[0] = 0;

       dp[1] = 1;

       for(int i = 2; i<n+1;i++)

       {

        dp[i] = dp[i-2] + dp[i-1];

       }

       for (int i : dp) {

         System.out.print(i+" ");

       }

    }

}