public class DPBasic{ /* 1. Whether problem can be solved using optimal substructure 2. If yes, are there any sub problems overlapping? 3. If yes, find the dp state and create dp expression 4. Then perform dp initialization / find out base condition 5. Find out time complexity and space complexity */ public int fab( int N){ int[] dp = new int[N+1]; for(int i = 1; i < dp.length; i++) dp[i] = -1; return fabUsingDP(N,dp); } //memoization - Bottom up approach - Least value first higest value later public int fabUsingDP(int N, int[] dp){ if(N <= 1) return N; //Assumption or dp state - we need to find fact value of particular N if(dp[N] == -1) return dp[N] = fabUsingDP[N-1] + fabUsingDP[N-2]; // Main logic or dp expression return dp[N]; } //Tabulation(iterative) - Top down approach - Highest value first and Least value later public int fabUsingDP2(int N, int[] dp){ dp[0] = 0; for(int i = 1; i < dp.length; i++ ){ if(dp[i] == -1) dp[i] = dp[i-1] + dp[i-2]; } return dp[N]; } /* Time complexity: O(N) Space complexity: O(N) */ }