动态规划，遍历方法

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]; 
}