PO88前两数之和

本文主要是介绍PO88前两数之和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：回溯+剪枝

#include<vector>
#include<string>
#include<limits.h> 

using namespace std;

class Solution {
public:
    bool backtrack(vector<int>& list, string num, int length, int index, long long sum, int prev) {
        if (index == length) {
            return list.size() >= 3;
        }
        long long curr = 0;
        for (int i = index; i < length; i++) {
            if (i > index && num[index] == '0') {
                break;
            }
            curr = curr * 10 + num[i] - '0';
            if (curr > INT_MAX) {
                break;
            }
            if (list.size() >= 2) {
                if (curr < sum) {
                    continue;
                }
                else if (curr > sum) {
                    break;
                }
            }
            list.push_back(curr);
            if (backtrack(list, num, length, i + 1, prev + curr, curr)) {
                return true;
            }
            list.pop_back();
        }
        return false;
    }
};
int main(){
    Solution solution;
    string str;
    cin>>str;
    vector<int>list;
    if(solution.backtrack(list, str, str.length(), 0, 0, 0)){
        cout<<"true"<<endl;
    }else{
        cout<<"false"<<endl;
    }
    return 0;
}

-[1]842. 将数组拆分成斐波那契序列

这篇关于PO88前两数之和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！