easy step by step interview thought process with recursion solution
lets take 10 as an example.\nFirst thing came up to my mind was that the problem can break down as \n\nint result = Math.max(2 * integerBreak(10 - 2) * i, 3 * i
lets take 10 as an example.\nFirst thing came up to my mind was that the problem can break down as \n```\nint result = Math.max(2 * integerBreak(10 - 2) * i, 3 * integerBreak(10 - 3), 4 * integerBreak(10 - 4)...)\n```\n\nSo we have our solution as,\n```\npublic int integerBreak(int n) {\n\tif (n <= 2) return 1;//base case\n\tint solution = 0;\n\tfor(int i = 2; i<n; i++) {\n\t\tsolution = Math.max(solution, i * integerBreak(n-i));\n\t}\n\treturn solution;\n}\n```\n\nHowever, after plug a couple number in, we will soon find out that our answer is wrong.\nFor example, plug in 4 would yield `2 * integerBreak(4-2)` which leads to `2 * 1 = 3`, because our base case is `if (n <= 2) return 1;` which is correct if the input is 2, but not if it is greater than 2. \n\nSo, we have a corner case to take care.\n\nAfter some experiment, it\'s not hard to see that when n <=4, n always bigger than break down product. Hence, our algorithm could be improved as follow.\n```\npublic int integerBreak(int n) {\n\tif (n <= 2) return 1;//base case\n\tint solution = 0;\n\tfor(int i = 2; i<n; i++) {\n\t\tif(n-i <= 4) solution = Math.max(solution, i * (n-i));//the corner discussed above\n\t\telse solution = Math.max(solution, i * integerBreak(n-i));\n\t}\n\treturn solution;\n}\n```\n\nLast step, it is not hard to see that we have repeated calculation that could be cached.\n```\npublic int integerBreak(int n) {\n\treturn integerBreak(n, new int[n+1]);\n}\n\npublic int integerBreak(int n, int[] cache) {\n\tif (n == 2) return 1;\n\tif(cache[n] > 0) return cache[n];//we have calculated the result before, so return it\n\tint solution = 0;\n\tfor(int i = 2; i<n; i++) {\n\t\tif(n-i<=4) {\n\t\t\tsolution = Math.max(solution, i * (n-i));\n\t\t}else {\n\t\t\tsolution = Math.max(solution, i * integerBreak(n - i, cache));\n\t\t}\n\t}\n\tcache[n] = solution;//cache the result\n\treturn solution;\n}\n```\n\n
[]