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

Question

问题陈述 =>

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

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

2：将 N 的值减 1。

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

这是更好理解的链接。 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 的 1 种可能性的解决方案不同于 2 的可能性，因为在第一个可能性中，我必须遍历 4->3->2，这里 2 的解决方案是 2，而在第二种可能性中，我们遍历 4->2 和 2 的解决方案这里是 1 现在这 2 个相同的子问题由于从上到下求解而具有不同的值。现在我在这里完全糊涂了。请有人帮我解决这个问题。

标签： algorithmdata-structuresqueuedynamic-programming

Answer 1

数字 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;
}