将n减少到1的最小步骤（变体）

Question

给定数字X，您可以执行以下操作之一：

1 - 减少X乘以1。

2 - 递增X乘以1。

3 - 如果X是3的倍数，则可以将X除以3。

我认为这个问题有一个O（n）dp解决方案，但如何解决1 <= x <= 10 ^ 9？

Answer 1

这适用于O（2log_3N）时间（如果N~3 ^ n，则需要~2n），因为每次移动都是：

• n mod 3 == 0：除以3
• n mod 3 == 1：减1
• n mod 3 == 2：加1

所以我们最多需要2次移动才能减少3倍，我们需要做n次。

<input type='number' id='nm'/>
<button onclick='go();'>Go</button>
<br>
<span id='out'/>
<script>

function go() {
var n=nm.value;
var nc=0;
out.textContent=n;
while (n>1) {
  n3=n%3;
    switch (n3) {
      case 0: {n/=3;break;}
      case 1: {n--;break;}
      case 2: {n++;break;}
    }
  nc++;
  out.textContent+=','+ n;
  }
out.textContent+=' ::'+ nc;
}

</script>