Untitled
unknown
java
a year ago
3.2 kB
71
Indexable
import java.util.Scanner; class Main { // leetcode 62 ================================================ public int up_rec(int i, int j, int n, int m){ if(i==n-1 && j==m-1){ return 1; } int rightPaths = 0; int downPaths = 0; if(j+1 < m){ rightPaths = up_rec(i,j+1,n,m); } if(i+1 < n){ downPaths = up_rec(i+1,j,n,m); } int totalPaths = rightPaths + downPaths; return totalPaths; } public int up_memo(int i, int j, int n, int m, int[][] dp){ if(i==n-1 && j==m-1){ return dp[i][j] = 1; } if(dp[i][j] != -1){ return dp[i][j]; } int rightPaths = 0; int downPaths = 0; if(j+1 < m){ rightPaths = up_rec(i,j+1,n,m); } if(i+1 < n){ downPaths = up_rec(i+1,j,n,m); } int totalPaths = rightPaths + downPaths; return dp[i][j] = totalPaths; } public int up_tab(int i, int j, int n, int m, int[][] dp){ for(int i=n-1; i>=0; i--){ for(int j=m-1; j>=0; j--){ if(i==n-1 && j==m-1){ dp[i][j] = 1; continue; } int rightPaths = 0; int downPaths = 0; if(j+1 < m){ rightPaths = dp[i][j+1]; //up_rec(i,j+1,n,m); } if(i+1 < n){ downPaths = dp[i+1][j]; //up_rec(i+1,j,n,m); } int totalPaths = rightPaths + downPaths; dp[i][j] = totalPaths; } } return dp[0][0]; } public int uniquePaths(int n, int m) { int[][] dp = new int[n][m]; for(int[] d: dp){ Arrays.fill(d,-1); } return up_memo(0,0,n,m, dp); } // fibonacci ================ public static int fibonacci_rec(int n){ if(n == 0 || n==1){ return n; } int ans = fibonacci_rec(n-1) + fibonacci_rec(n-2); return ans; } public static int fibonacci_memoization(int n, int[] memo){ if(n == 0 || n==1){ // memo[n] = n; return memo[n] = n; } if(memo[n] != -1){ return memo[n]; } int ans = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo); return memo[n] = ans; } public static int fibonacci_tabulation(int N, int[] dp){ for(int n=0; n<=N; n++){ if(n == 0 || n==1){ dp[n] = n; continue; } int ans = dp[n-1] + dp[n-2]; //fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo); dp[n] = ans; } return memo[N]; } public static void main(String[] args){ int n = 5; // int nFibTerm = fibonacci_rec(n); int[] memo = new int[n+1]; Arrays.fill(memo, -1); int nFibTerm = fibonacci_memoization(n, memo); System.out.println(nFibTerm); } }
Editor is loading...
Leave a Comment