day31 | 一探动规

刚开始的动规几道题基本都是爬楼梯的变形。

*****************

这题主要问题的到达的是下标为 n 的位置而不是n-1,所以列 dp 的时候空间要给大一下。

然后既然到 fib 数了就复习一下尾递归的知识.

常规递归的过程是:每次函数调用时需要记录当前函数上下文的信息,包括传入参数、局部变量值等,并将这些信息保存在栈空间(也称调用栈或运行时栈)中。

举个例子来说。

- 当一个函数 fib 返回值是 fib(n-1)+fib(n-2)时,函数结束前需要执行相加的操作,所以编译器不会丢弃掉这些信息。

- 而如果返回值是fib(n-1,ret2,ret1+ret2)就不用保存原函数的信息,就可以减少栈空间,防止stackoverflow

全部评论

相关推荐

#include <iostream>#include <sstream>#include <vector>#include <set>#include <algorithm>using namespace std;vector<string> convert(const vector<string>& strs) {    vector<string> result;    for (const string& str : strs) {        set<char> characters;        for (char c : str) {            characters.insert(tolower(c));        }        string sortedStr(characters.begin(), characters.end());        result.push_back(sortedStr);    }    return result;}void solution(const string& aim, const string& check) {    stringstream ss1(aim), ss2(check);    string token;    vector<string> seq1, seq2, split;    while (getline(ss1, token, ',')) {        seq1.push_back(token);    }    while (getline(ss2, token, ',')) {        seq2.push_back(token);        split.push_back(token);    }    vector<string> convertedSeq1 = convert(seq1);    vector<string> convertedSeq2 = convert(seq2);    vector<string> res;    for (const string& s1 : convertedSeq1) {        for (size_t i = 0; i < convertedSeq2.size(); i++) {            if (s1 == convertedSeq2[i] && find(res.begin(), res.end(), split[i]) == res.end()) {                res.push_back(split[i]);            }        }    }    if (res.empty()) {        cout << "not found" << endl;    }    else {        for (size_t i = 0; i < res.size(); i++) {            cout << res[i];            if (i != res.size() - 1) {                cout << ",";            }        }        cout << endl;    }}int main() {    string aim, check;    getline(cin, aim);    getline(cin, check);    solution(aim, check);    return 0;}
查看3道真题和解析
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务