I mean that '+' is last operator for execute.

dp[11] you can build expression '11'
dp[14] you can build expression '(11 + 1 + 1 + 1) * 1' that is shortest expression with '*' at the top. and '11 + 1 + 1 + 1' is the shortest expression with '+' at the top.

dp[1] = { 1, 1 }
dp[11] = { 2, 2 }
dp[111] = { 3, 3 }
dp[1111] = { 4, 4 }

Let's say you need get answer for num = 123. How 123 can be get? 121 + 2, 3 * 41, 51 + 72 and so on. In order to calc dp[123][0] you need to iterate over all possible terms. Let's say that 123 = l + r. Both l and r < 123. So you can reccursively calculate dp[l] and dp[r].

You calculated them and you need to construct the shortest expression. Neither of terms need to be wrapped in brackets, so dp[123][0] = min(dp[l][0], dp[l][1]) + 1 + min(dp[r][0], dp[r][1]).

Analogically you can calculate dp[123][1]. But factors can be wrapped in brackets (this adds 2 to answer). For example, 123 = 3 * 41. 3 = 1 + 1 + 1. You can't tell that 123 = 1 + 1 + 1 * 41. But you can tell 123 = (1 + 1 + 1) * 41. That because (1 + 1 + 1) has '+' on the top. With such reasoning you can calculate transitions.

For each n there is iterating over O(n) possible terms and O(sqrt(n)) possible factors. So the whole complexity is O(n^2).