Learning DP

S-C-U-B-E · S-C-U-B-E · commit eaa95f27472b · 2020-03-15T19:00:41.000+05:30
diff --git a/src/Coin_Change.java b/src/Coin_Change.java
@@ -0,0 +1,39 @@
+//LEET CODE
+
+import java.io.*;
+import java.util.Arrays;
+
+public class Coin_Change {
+    public static void main(String[] args)throws IOException {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+
+        int t = Integer.parseInt(br.readLine());
+        while(t-- > 0){
+            String[] s = br.readLine().split(" ");
+
+            int len = s.length;
+            int[] a = new int[len];
+            for(int i=0; i<len; i++){a[i] = Integer.parseInt(s[i]);}
+
+            int sum = Integer.parseInt(br.readLine());
+
+            int ans = coinChange(a, sum);
+            System.out.println(ans);
+        }
+    }
+
+    private static int coinChange(int[] a, int sum){
+        int[] dp = new int[sum+1];
+        Arrays.fill(dp,sum+1);
+        dp[0] = 0;
+
+        for(int i=0; i<=sum; i++){
+            for(int j:a){
+                if(j <= i)
+                    dp[i] = Math.min(dp[i - j]+1,dp[i]);}
+
+        }
+
+        return dp[sum] > sum ? -1 : dp[sum] ;
+    }
+}
diff --git a/src/FIBONACCI_logN.java b/src/FIBONACCI_logN.java
@@ -0,0 +1,60 @@
+//Codechef//Easy Tiling
+import java.io.*;
+
+public class FIBONACCI_logN {
+
+    static long MOD = 1000000007;
+    public static void main(String[] args)throws IOException {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+
+        int t = Integer.parseInt(br.readLine());
+        while(t-- > 0) {
+            long n = Long.parseLong(br.readLine());
+
+            if(n == 1) System.out.println(1);
+            else if(n == 2) System.out.println(2);
+            else{
+                n--;
+                long[][] M = {{1,1},{1,0}};
+                long[][] Identity = {{1,0},{0,1}};
+                long[] f = {1,1};
+                while(n > 0){
+                    if((n & 1) == 1){
+                        Identity = multiply(Identity,M);
+                    }
+                    M = multiply(M,M);
+                    n = n >> 1;
+                }
+
+                //HERE F(0) = 1; F(1) = 1 THATS WHY F(2) = 2 AND SO ON..
+                long ans = (Identity[0][0] + Identity[0][1])%MOD; // Fibonacci(N)
+                System.out.println(ans);
+/*
+                long ans = (Identity[1][0] + Identity[1][1])%MOD; // Fibonacci(N - 1)
+                System.out.println(ans);*/
+
+                //FOR F(0) = 0; F(1) = 1;
+                /*long ans = (Identity[0][0])%MOD; // Fibonacci(N)
+                System.out.println(ans);
+
+                long ans = (Identity[1][0])%MOD; // Fibonacci(N - 1)
+                System.out.println(ans);*/
+            }
+
+        }
+    }
+
+    private static long[][] multiply(long[][] A,long[][] B){
+        long a = (A[0][0]*B[0][0] + A[0][1]*B[1][0])%MOD;
+        long b = (A[0][0]*B[0][1] + A[0][1]*B[1][1])%MOD;
+        long c = (A[1][0]*B[0][0] + A[1][1]*B[1][0])%MOD;
+        long d = (A[1][0]*B[0][1] + A[1][1]*B[1][1])%MOD;
+
+        A[0][0] = a;
+        A[0][1] = b;
+        A[1][0] = c;
+        A[1][1] = d;
+
+        return A;
+    }
+}
