343. Integer Break

343. Integer Break

https://leetcode.com/problems/integer-break/

문제

풀이(DP)

n = 1일 때 => 1
n = 2일 때 => 1 + 1, 1*1 = 1
n = 3일 때 => 1 + 2, max(1x2, 1x1x1) = 2(2+1은 제외한다)
n = 4일 때 => 1 + 3, 2 + 2가 될 수 있고 곱셈에서는 max(1x3, 1x1x2) or max(2x2, 2x1x1) = 4이다.
즉 점화식으로 나타내면 dp[i] = max(dp[i], ix(j-i), i x dp[j-i])로 나타낼 수 있다.

안쪽 for문에서 (1, i // 2 +1)한 이유는 절반 이상에서는 필요가 없기 때문이다.
즉 8로 예를 들어보면 for j in range(1, 5)가 되는데
(1,7) (2,6) (3,5) (4,4)까지 된다. 그 이후 부터는 이전에 값과 동일하기 때문에 제외해주었다. 그리고 점화식을 사용해서 dp테이블을 완성하였다.

결과(DP)