刷题：递归问题与动态规划

灰太狼 2021-12-19 01:47 284阅读 0赞

#include<iostream>
    #include<vector>
    using namespace std;
    
    /**************************************
    *        
    *        斐波那契问题的三种解法
    *
    ***************************************/
    //方法1：递归调用函数,时间复杂度 = 2^N
    int Fibonacci_fun1(int n)
    {
    	if (n < 1)
    		return 0;
    	else if (n == 1 || n == 2)
    		return 1;
    	else
    		return Fibonacci_fun1(n - 1) + Fibonacci_fun1(n - 2);
    }
    //方法2：非递归方法，时间复杂度 = N
    int Fibonacci_fun2(int n)
    {
    	if (n < 1)
    		return 0;
    	else if (n == 1 || n == 2)
    		return 1;
    	else
    	{
    		int res = 1;
    		int pre = 1;
    		int temp = 0;
    		for (int i = 3; i <= n; ++i)
    		{
    			temp = res;
    			res = pre;
    			pre = pre + temp;
    		}
    
    		return pre;
    	}
    }
    //方法3：矩阵乘法，时间复杂度 = logN
    vector<vector<int>> Mat_multip(vector<vector<int>> m, vector<vector<int>> n)
    {
    	vector<vector<int>> res(m.size());
    	for (int i = 0; i < m.size(); ++i)
    		res[i].reserve(2);
    	int temp = 0;
    	for (int i = 0; i < m.size(); ++i)
    	{
    		 
    		for (int j = 0; j < n.at(0).size(); ++j)
    		{
    			temp = 0;
    			for (int k = 0; k < m.at(0).size(); ++k)
    			{
    				temp += m.at(i).at(k)*n.at(k).at(j);
    				
    			}
    			res.at(i).push_back(temp);
    		}
    		
    	}
    	
    	return res;
    }
    
    vector<vector<int>> MatPower( vector<vector<int>> m, int n)
    {
    	vector<vector<int>> res = { {1,0},{0,1} };
    	vector<vector<int>> temp = m;
    
    	for (; n != 0; n >>= 1)
    	{
    		if ((n & 0x1) == 1)
    			res = Mat_multip(res, temp);
    		temp = Mat_multip(temp, temp);
    	}
    	return res;
    }
    
    
    
    int Fibonacci_fun3(int n)
    {
    	if (n < 1)
    		return 0;
    	else if (n == 1 || n == 2)
    		return 1;
    	else
    	{
    		vector<vector<int>> base = { { 1,1 },{ 1,0 } };
    		vector<vector<int>> res;
    		res = MatPower(base, n - 2);
    		return res[0][0] + res[1][0];
    
    	}
    }
    
    
    
    
    int main()
    {
    
    	cout << "Fibonacci_fun2: " << Fibonacci_fun3(40) << endl;
    	cout << "Fibonacci_fun2: " << Fibonacci_fun2(40) << endl;
    	cout << "Fibonacci_fun1: " << Fibonacci_fun1(40) << endl;
    	
    
    
    	return 0;
    }