LEET Code 21 Days of Dynamic Programming

#coding #leetcode #java #dynamicprogramming

** Day 13**
Minimum falling Path
using hashmap

Day 10

Airtmetic Slices
Logic and other Solution: LeetCode

package Day10;
import java.util.Scanner;

public class AirthmeticSlice {
        public static int numberOfArithmeticSlices(int[] nums) {
         int[] DP= new int[nums.length]; 
         int count=0;
            for(int i=2; i<nums.length; i++){
            int diff=nums[i]-nums[i-1];
            if(diff==nums[i-1]- nums[i-2]){
                //previous series grown +1 new ap
                DP[i]=DP[i-1]+1;
             count=DP[i]+count;
            } ;

            }
           return count;
        }
 public static void main(String[] args) {
     Scanner sc= new Scanner(System.in);
     System.out.println("Enter the length of your array");
     int n= sc.nextInt();
     int[] nums= new int[n];
     for(int i=0; i<n; ++i){
     nums[i]=sc.nextInt();
     sc.close();

     }
System.out.println(numberOfArithmeticSlices(nums));
 }
    }

Decode Ways :
LeetCode Solution :

we can use subString Intger.Parseint(s.substring(i-1, i+1), a point to be noticed i-1 to i+1, will cover range of i-1 and 1. eg:(2,5)-> 2,3,4

Day 5

Day 4

public class jumpGame {
      //I will store my maximum value in Dp array and compare the current maximum dp[i] to 
    //the previous maximum Dp[i-1], so the currrent maximum or the maximum value will depend on the value of dp[i-1], so we can store dp[i-1] in variable MaxJump
//maxJump= Math.max(maxJump, nums[i]+i);
    public static boolean canJump(int[] nums) {
        if (nums.length==1) return true;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(dp[i - 1] < i){
                return false;
            }
             //if my capcity to jump is smaller than to capacity to reach last index,i, then we will return false 
            dp[i] = Math.max(dp[i - 1], i + nums[i]);
            //maxJump= Math.max(maxJump, i+nums[i]);
        //whether we can reach to end index or not from current: i+nums[i]
        }

        return true;

    }   
     public static void main(String[] args ){
         int[] nums= {2,1,4,3,0,1};
        System.out.println(canJump(nums));
    }
}

Day 3

Day 2:

Day 1

Problem 1: Fibonacci Series

class Solution {
    public int fib(int n) {
        if(n==0 || n==1) return n;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1] =1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
}

Problem 2: n-th tribonacci Series



class Solution {
    public int tribonacci(int n) {
        if(n==0 ){
            return 0;
        }
        else if(n==1 || n==2){
            return 1;
        }
        int dp[]= new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for(int i =3;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];