动态规划，遍历方法

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向量已经包含 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];
}