動態規劃，遍歷方法

Question

int fib(int numb){ 
    vector<int> temp; 
    int str; 
    if(numb==0 || numb==1){ 
     return numb; 
    } 
    else{ 
     str=(fib(numb-1)+fib(numb-2)); 
     temp.push_back(str); 
     return str; 
    } 
    for(int i=0;i<temp.size();i++){ 
    if(temp[i]==numb){ 
      return temp[i]; 
     }} 

斐波那契函數和它的工作，但我如何檢查功能的for循環部分是否真的工作？它的一種遍歷方法是查找現有數字並返回它，而不是處理另一個遞歸。

Answer 1

你的循環不可能工作。它永遠不會工作。因爲沒有辦法進入循環。循環前的每個代碼路徑以return語句結束。

瀏覽你的代碼，聲明語句，親眼看看你的代碼永遠不會到達循環。

Answer 2

您必須在返回任何值之前處理存儲的元素。更重要的是，當您在遞歸調用期間將元素存儲在矢量中時，矢量temp必須是靜態的。

而研究不應該是這樣的：你應該在向量中存儲的值，不同地說，你想要什麼temp[i]是fib(i)。

一個簡單的方法是使用C++允許通過函數初始化靜態值。然後，您可以初始化temp爲{0,1}，當問及對於一個數值，只是看是否高於temp.size：

• 如果是，計算，並將其存儲到temp - 使用計算機。它們的值爲fib（n-1）和fib（n-2），當你計算它時，你知道temp vector已經包含fib（n-1），並且不包含fib（n）=>只是把它推回temp
• 它不只是從temp

有限公司解壓德可能是：

// return a temporary vector containing 0 and 1 
std::vector<int> inifib() { 
    std::vector<int> t; 
    t.push_back(0); 
    t.push_back(1); 
    return t; 
} 
int fib(unsigned int numb) { 
    static std::vector<int> temp = inifib(); // initialize once the static temp with size 2 and values 0,1 
    if (numb >= temp.size()) { 
     int cr = fib(numb-1) + fib(numb - 2); 
     temp.push_back(cr); // when we are here, temp contains everything up to fib(numb - 1) - just push 
    } 
    return temp[numb]; 
}