Java 4 lines recursion, with step-by-step explanation to derive DP


  • 27
    Y

    We use i steps to reach maxA(i) then use the remaining n - i steps to reach n - i - 1 copies of maxA(i)

    For example:
    A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
    Here we have n = 7 and we used i = 3 steps to reach AAA
    Then we use the remaining n - i = 4 steps: Ctrl A, Ctrl C, Ctrl V, Ctrl V, to reach n - i - 1 = 3 copies of AAA

    We either don't make copies at all, in which case the answer is just n, or if we want to make copies, we need to have 3 steps reserved for Ctrl A, Ctrl C, Ctrl V so i can be at most n - 3

        public int maxA(int n) {
            int max = n;
            for (int i = 1; i <= n - 3; i++)
                max = Math.max(max, maxA(i) * (n - i - 1));
            return max;
        }
    

    Now making it a DP where dp[i] is the solution to sub-problem maxA(i)

        public int maxA(int n) {
            int[] dp = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                dp[i] = i;
                for (int j = 1; j <= i - 3; j++)
                    dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
            }
            return dp[n];
        }
    

  • 6
    F

    The inner loop of the bottom-up DP can be truncated to at most four terms, that is, for dp[i], we only need to choose the largest one from dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4, dp[i - 6] * 5, while all the rest terms like dp[i - 7] * 6, dp[i - 8] * 7, ... can be ignored. The reason is as follows: when computing dp[i - 3], we've already chosen its value to be the maximum of terms like dp[i - 6] * 2, dp[i - 7] * 3, dp[i - 8] * 4, ..., which implies dp[i - 3] >= dp[i - k] * (k - 4) for k >= 6. This further leads to dp[i - 3] * 2 >= dp[i - k] * (2k - 8) >= dp[i - k] * (k - 1) if k >= 7. So we always have dp[i - 3] * 2 >= dp[i - 7] * 6, dp[i - 3] * 2 >= dp[i - 8] * 7, .... Therefore terms like dp[i - 7] * 6, dp[i - 8] * 7, ... won't contribute when evaluating dp[i].

    The truncation will make the DP solution run effectively in O(n) time. Also the space complexity can be reduced to O(1) since now we only need to maintain a constant number of variables (seven, I would say, dp[i], dp[i-1], dp[i-2], dp[i-3], dp[i-4], dp[i-5], dp[i-6]). The following is the modified code:

    public int maxA(int N) {
        int[] dp = new int[7];
        	
        for (int i = 1; i <= N; i++) {
        	dp[0] = i;
        		
        	for (int k = 6; k > 2; k--) {
        	    dp[0] = Math.max(dp[0], dp[k] * (k - 1));
        	}
        		
        	for (int k = 6; k > 0; k--) {
        	    dp[k] = dp[k - 1];
        	}
        }
        	
        return dp[0];
    }
    

  • 1
    J

    Can anyone explain why n-i-1 represents copies of maxA(i)? Like what's the math behind this?


  • 10

    @jyc123 'cause after you use i steps to reach maxA(i), you still have n -i steps. then you cost 2 more steps to do Ctrl-A and Ctrl-C, After this you have n-i-2 steps left, all the rest could be used to do Ctrl-V, so you increase n-i-2 copies, at last, you have the original copy, you need add it to the total num of copies. therefore, you have n-i-1 copies


  • 0
    X

    @wxl163530 Very clear explanation. Thx!


  • 0

    Hi, Thank you for your sharing! Could you please give a proof why multiple use of Key2 won't comes more 'A's than one time usage?


  • 0
    A

    @fun4LeetCode
    Hi, could you please explain why should we consider all last 6 results not the last 3 results? Thank you so much!


  • 0
    F

    @AmyXyy Hi AmyXyy. I actually saw some people propose that we only need to consider the second, third and fourth ones. But there is no easy way to prove that. Considering the middle three results or all six results does not make a difference regarding the time complexity, though the former may be more efficient for large N.


  • 0
    X

    @jyc123
    it is actually (n - i - 2 + 1)
    2 is (ctrl A and ctrl C)
    n - i - 2 is how many times of the (ctrl v)
    +1 is you need to count the been copied original one


  • 0
    I
        public int maxA(int n) {
            int[] dp = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                dp[i] = i; // I feel like dp[i] = dp[i - 1] + 1 is more reasonable
                // because dp[i] might come from ..., ..., CTRL-V then append an A
                // even though we can prove it's impossible
                for (int j = 1; j <= i - 3; j++)
                    dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
            }
            return dp[n];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.