如何解决动态规划中的重叠子问题

Question

问题陈述=>

您有疑问。每个查询由一个数字 N 组成。您可以在每次移动中执行以下 2 个操作中的任何一个：

1：如果我们取2个整数a和b，其中N=a*b (a>1,b>1)，那么我们可以改变N=max(a,b)。

2：将N的值减1。

确定将 N 的值减少到 0 所需的最少移动次数。

这里是link为了更好的理解。 https://www.hackerrank.com/challenges/down-to-zero-ii/problem

我知道这里有一些重叠的子问题，我们可以使用DP来一次又一次地忽略相同子问题的计算。

现在，我的问题是在这个问题中，相同的子问题如何有相同的解决方案。因为我们必须从上到下解决这个问题，如果我们从下到上解决它们，子问题有相同的解决方案。

例如

N=4
1 possibility = 4->3->2->1->0
2 possibility = 4->2->1->0

现在在以上两种可能性中，2是重复的，我可以使用DP，但我如何存储它们的值。我的意思是，在第一种可能性中，2 的解决方案与第二种可能性不同，因为在第一种可能性中，我必须遍历 4->3->2，这里 2 的解决方案是 2，而在第二种可能性中，我们遍历 4->2 和 2 的解决方案这是 1 现在这 2 个相同的子问题由于从上到下的求解而具有不同的值。现在我在这里完全困惑。请有人帮我解决这个问题。

Answer 1

编辑 2：

我认为这是解决您问题的方法。解决方案在JavaScript:

// ****************************************************************************
function findPaths(tree, depth = 0, path = [], paths = [-1, []]) {
  const [node, children] = tree

  path.push(node)

  if (!children) {
    // console.log(path, depth)
    if (paths[0] === -1 || paths[0] > depth) {
      paths[0] = depth
      paths[1] = [paths.length]
    } else if (paths[0] === depth) {
      paths[1].push(paths.length)
    }

    paths.push([...path])
    path.pop()
    return
  }

  children.forEach((el) => {
    findPaths(el, depth + 1, path, paths)
  })

  path.pop()

  return paths
}

// ****************************************************************************
function downToZero(n) {
  const tree = [n]
  const divisors = []

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
      divisors.push(Math.max(i, n / i))
    }
  }

  if (divisors.length) {
    tree.push(divisors.map(downToZero))
  } else if (n > 0) {
    tree.push([downToZero(n - 1)])
  }

  return tree
}

// ****************************************************************************
function printPaths(paths) {
  console.log('Total number of solutions:', paths.length - 2)
  console.log('Total number of solutions with minimal moves:', paths[1].length)
  console.log('Minimal moves:', paths[0])

  paths[1].forEach((pathIndex) => {
    let printPath = ''

    paths[pathIndex].forEach((element) => {
      printPath = `${printPath}${printPath === '' ? '' : '->'}${element}`
    })
    console.log(printPath)
  })
  console.log('')
}

// ****************************************************************************
// Test
printPaths(findPaths(downToZero(812849)))
printPaths(findPaths(downToZero(100)))
printPaths(findPaths(downToZero(19)))
printPaths(findPaths(downToZero(4)))

Answer 2

数字 N 的解应该存储使它成为 0 所需的最少步骤这就是解决方案的样子

int dp[1000001];
memset(dp,-1,sizeof(dp);
int sol(N){
if(N == 2){
  return 2;
}
if(dp[n]!=-1){
 return dp[n]'
}
int sol = 1+sol(min(move1,move2));
dp[n] = sol ;
return sol;
}

如何解决动态规划中的重叠子问题

how to solve the overlapping sub problems in Dynamic programming

algorithm

queue

dynamic-programming

data-structures