650. 2 Keys Keyboard

Problem Link : https://leetcode.com/problems/2-keys-keyboard/
----------------------------------------------------------------
Complexity: Time=O(N^2), Memory-O(N^2), TimeTaken-<1hr
----------------------------------------------------------------
Logic-
As we know that at max there can be n steps, hence n^2 space.
In each traversing we either copy or paste.
If we copy then set the flag to false otherwise this code will go in infinite loop.
Hence using flag. And if we paste we set the flag to true. And do the loop.

class Solution {
    int goal;
    int[][] dp;
    public int minSteps(int n) {
        if(n==1)return 0;
        goal=n;
        dp=new int[n+1][n+1];
        for(int i=0;i<=n;i++)
            Arrays.fill(dp[i], -1);
        
        return 1+traverse(1, 1, true);
    }
    private int traverse(int n, int copy, boolean copied){
        // System.out.println(n+" "+ copy);
        if(n==goal)return 0;
        if(dp[n][copy]!=-1)return dp[n][copy];
        int val=goal;
        if((n+copy)<=goal)
            val=1+traverse(n+copy, copy, true);
        if(copied)
            val=Math.min(val, traverse(n, n, false)+1);
        
        dp[n][copy]=val;
        return val;
    }
}