algorithm - 给定 N，生成所有以 0 开头并以 N 结尾的序列，并且相邻元素之间的差异是 2 的幂 - 在动态规划中

Question

我在标题中有问题，我不知道如何使用 DP 优化解决方案。例如，给定 N=5，所有序列将是：

[0 1 2 3 4 5]
[0 1 2 3 5]
[0 1 2 4 5]
[0 1 3 4 5]
[0 1 3 5]
[0 1 5]
[0 2 3 4 5]
[0 2 3 5]
[0 2 4 5]
[0 4 5] 

我使用递归https://play.golang.org/p/i2aCQBF01m_T解决了它，有很多计算重复，我不知道如何对其进行动态编程。

例如在：

[0 1 2 3 4 5]
[0 1 3 4 5]

结束部分3 4 5计算两次。

我想有一张这样的地图，map[int][][]int但在我看来，空间消耗是错误的。

标签： algorithmdynamic-programming

Answer 1

function getSeqs(n) {
  let seqs = [[0]]
  for (let i = 1; i <= n; i++) {
    seqs.push([])
    for (let j = 1; j <= i; j *= 2) {
      seqs[i] = seqs[i].concat(seqs[i - j].map(t => t * 10 + i))
    }
  }
  return seqs[n].map(t => '0' + t)
}

console.log(getSeqs(5))