遞歸解決方案的動態編程解決方案

給定輸入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來完成這項工作，因爲我對此很虛弱。

來源

2014-09-21 g4ur4v

或者你可以用分析方法計算它：'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）。

來源

2014-09-21 19:50:18 Ian

嗨，謝謝你的回答。我意識到這個解決方案，但我只是在尋找解決方案，使用'動態編程'。 – 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）次

我想也許這是你想要的。

來源

2014-09-25 07:47:07 mickeyandkaka

遞歸解決方案的動態編程解決方案

回答

相關問題