递归解决方案的动态编程解决方案

问题描述：

给定输入n，找到所有可能的数字组合1 ... n的总和。例如，如果n=3，那么所有可能的组合是递归解决方案的动态编程解决方案

(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)

和它们的总和是

1 + 2 + 3 + (1+2) + (1+3) + (2+3) + (1+2+3) =24

我能解决使用recursion这个问题。我如何使用Dynamic Programming来解决这个问题？

#include<iostream> 
using namespace std; 
int sum=0,n; 
int f(int pos,int s) 
{ 
    if(pos>n) 
    { 
     return 0; 
    } 
    else 
    { 
     for(int i=pos+1;i<=n;++i) 
     { 
      sum+=s+i; 
      f(i,s+i); 
     } 
    } 
} 
int main() 
{ 
    cin>>n; 
    sum=0; 
    f(0,0); 
    cout<<sum<<'\n'; 

    } 
}

编辑虽然这个问题可以在固定的时间使用该series来解决。

但我想知道如何使用Dynamic Programming来完成这项工作，因为我对此很虚弱。

或者你可以用分析方法计算它：'n *（n + 1）* 2 **（n-2）'。没有循环，没有递归，没有动态编程。很高兴通过派生发布答案。 – NPE 2014-09-21 19:48:30

答

您不需要使用动态编程;如果你愿意，你可以使用简单的算术。

个案数量是2^n，因为每个数字对于给定的总和是打开或关闭的。

从1到n的每个数字只用于总和的一半，因此每个数字都是2 ^（n-1）次。 1 + 2 + ... + n =（n-1）* n/2.

因此，总和为（n-1）* n/2 * 2 ^（n-1）。 n = 3时，它是（4 * 3/2）×4 = 24

编辑：如果你真的想用动态规划，这里有一个方法。动态规划利用节约子问题的结果来解决超级问题。在这个问题中，子问题将是来自1 ... n-1的所有组合的总和。

因此，创建一个从n - >（组合数，组合数之和）的映射。

用1 - >（2,1）进行初始化。因为有两个组合{0,1}，总和为1.包含0只会使数学变得更容易一些。

然后你的迭代步骤是使用映射。让我们假设（n-1） - >（k，s），意思是对于1 ... n-1有k个和s的和。

然后n的集合数是k * 2（每个组合都有n或不）。并且所有组合的总和是s +（s + k * n），因为你有前面的总和（其中n是缺失的）加上所有组合的总和与n（应该是k * n大于s因为有k个新组合，每个都有n个）。

所以加上n - >（2 * k，2 * s + k * n）。

而你的最终答案是s中的n - >（k，s）。

嗨，谢谢你的回答。我意识到这个解决方案，但我只是在寻找解决方案，使用'动态编程'。 – g4ur4v 2014-09-21 19:56:42

答

让DP [N]是的结果，因此：

dp[1] = 1 
dp[n] = 2 * dp[n-1] + 2^(n-1) * n

首先，很明显，DP [1] = 1

其次，DP [n]是包含n个的总和（1）（2）（1,2）} + {（3），（1,3），（2,3），...，（1,2,3）}

我们可以发现dp [n-1]出现两次，n的出现次数为2 ^（n-1）次

我想也许这是你想要的。

递归解决方案的动态编程解决方案

相关推荐