Hint solution with explanation. DP O(n)


  • 0
    A

    By using the hint we can notice regularity if we check the answers from 7 to 10.
    d[6] = 9;
    d[7] = 12;
    d[8] = 18 = 3d[8-3];
    d[9] = 27 = 3
    d[9-3];
    d[10] = 36 = 3*d[10-3];
    d[i] = 3 * d[i-3];

    public class Solution {
        public int integerBreak(int n) {
            int d[] = new int[Math.max(n+1, 7)];
            d[2] = 1;
            d[3] = 2;
            d[4] = 4;
            d[5] = 6;
            d[6] = 9;
            for (int i=7; i<=n; i++) {
                d[i] = 3*d[i-3];
            }
            return d[n];
        }
    }
    

Log in to reply
 

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