# Tag Info

1

So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.

0

Lookup “depth first” and “breadth first” search. I’d guess you tried depth first and it fails. Try breadth first, and make sure that when a sequence can be produced in two or more ways, you ignore the second and further ways.

2

Here is an equivalent way to calculate $t(x,y,z)$. We distinguish between three cases: $x \leq z$: the answer is $y$. $x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise. $x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise. You ...

-1

Let's assume the optimal cut for 8 is: $8 = 1+2+3+2$. When $i=3$, it means you cut at length 3, and leave 5 as a second part. You can get the optimal value from $r_3$ and $r_5$, of course. But please be noted, you must have already get this optimal value when $i=1$. When $i=1$, $r_8 = r_1 + r_7$, where $r_7$ can give you optimal cut as $7 = 2+3+2$. ...

Top 50 recent answers are included