public class Solution { public static int ninjaTraining(int n, int points[][]) { // return solve(n-1 , points , 3 , new Integer[n][4]); int[][]dp = new int[n][4]; /* while writing tabulization go from base case to n in recursion solution 1) handle for base case 2)also include loops for changing states 3) rest same code as recursion just replace recursion calls by dp */ for(int i = 0 ;i < n ;i++){ for(int last = 0 ; last < 4 ; last++){ for(int j = 0 ; j < 3 ; j++){ if(j != last){ int point = points[i][j] + (i == 0 ?0 :dp[i-1][j]); //handling for base case dp[i][last] = Math.max(dp[i][last] , point); } } } } return dp[n-1][3]; //0-2 denotes activity , 3 denotes no last activity exist } //recursion + memoization public static int solve(int idx , int points[][] , int last , Integer[][] dp){ if(idx == 0){ int base = 0; for(int i = 0 ;i < 3 ; i++){ if(i != last) base = Math.max(base , points[0][i]); } return base; } if(dp[idx][last] != null) return dp[idx][last]; int max = 0; for(int i = 0 ;i < 3 ; i++){ if(i != last){ //we choose nth activity and send calls for rest of the ans; int point = points[idx][i] + solve(idx-1 , points , i , dp); max = Math.max(max , point); } } return dp[idx][last] = max; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter