左神算法中级班第五课[C++代码]

• 第一题：斐波那契数列的应用
• • 代码
• 第一题拓展：斐波那契数列的拓展应用
• 第五题
• 第六题：背包问题
• 第七题：
• • 代码

声明：博客根据左神在毕站的讲课视频整理，代码是根据左神的java代码版本改写为c++版本
代码为自己动手改写，未经应用不能转载

github代码链接：
(https://github.com/hjfenghj/zuoshen_middlecalss)

• 解法1
  找规律为斐波那契数列
• 解法2
• 递归

#include
#include
#include

using namespace std;

//递归加回溯写法
class PROBLEM01
{
public:
	//idx代表目前字符串的长度
	//s目前字符串
	//N目标长度
	int get_res(vector s, int N, int idx)
	{
		int ans = 0;
		//截至条件，每一个达到目标的叶节点
		if (s.size() == N)
			return 1;
		//上一个字符为'1'，下一个字符有两种情况
		if (s[idx - 1] == '1')
		{
			s.push_back('1');
			ans += get_res(s, N, idx + 1);
			//回溯
			s[idx] = '0';
			ans += get_res(s, N, idx + 1);

		}
		//上一个字符为'0',下一个字符只有一种情况
		if (s[idx - 1] == '0')
		{
			s.push_back('1');
			ans += get_res(s, N, idx + 1);
		}
		return ans;
	}

	int MAIN(int T)
	{
		int ans = 0;
		vector Arr1;
		Arr1.push_back('0');
		PROBLEM01 P1;
		ans = P1.get_res(Arr1, T, 1);
		Arr1[0] = '1';
		ans += P1.get_res(Arr1, T, 1);
		cout << ans << endl;
		return 0;
	}
};

//斐波那契数列写法,复杂度O(N)
class PROBLEM01_2
{
public:
	int get_res(int N)
	{
		vector res(N+1,0);
		res[0] = 1;
		res[1] = 2;
		for (int i = 2; i <= N; i++)
		{
			res[i] = res[i - 1] + res[i - 2];
		}
		cout << res[N] << endl;
		return 0 ;
	}
};


//斐波那契数列进阶模式，复杂度O(logN)
class PROBLEM01_3
{
public:
	int get_res(int N)
	{
		vector> M = { {1,1},{1,0} };//初始转换矩阵
		vector base = { 3,2 };//起始项
		
		vector> M_N1(M.size(), vector(M.size(), 0));//最终的转化矩阵
		//初始化为对角矩阵
		for (int i = 0; i < M.size(); i++)
			M_N1[i][i] = 1;

		int temp = N - 2;//转换矩阵需要N-2次方
		while (temp != 0)
		{
			if (temp & 1 == 1)
			{
				M_N1 = POW(M_N1, M);
				M = POW(M, M);
			}
			else
				M = POW(M, M);
			temp = temp >> 1;
		}

		vector res = DOT(base, M_N1);
		return res[0];
	}
	vector> POW(vector> Arr1, vector> Arr2)
	{
		vector> res(Arr1.size(),vector(Arr2[0].size(),0));
		for (int i = 0; i < Arr1.size(); i++)
		{
			for (int j = 0; j < Arr2.size(); j++)
			{
				for(int k=0;k DOT(vector Arr, vector> M)
	{
		int L = Arr.size();
		vector res(L, 0);
		for (int i = 0; i < L; i++)
		{
			for (int j = 0; j < L; j++)
			{
					res[i] += Arr[j] * M[j][i];
			}
		}
		return res;
	}
	
};

int main()
{
	int T = 4;
	PROBLEM01 P;
	P.MAIN(4);
	PROBLEM01_2 P2;
	P2.get_res(4);
	PROBLEM01_3 P3;
	cout << P3.get_res(4) << endl;
	return 0;
}

技巧：求矩阵的N次方，求一个数的N次方(二进制方法加速求解N次方)
凡是可以写为固定公式的题目，都可以使用斐波那契数列求解，但是如果题目让求第1亿项的话，就需要遍历好久；这里提出一个时间复杂度为O(1)的解法；

实践： 一只母牛，人工授精，每年生一只母牛，母牛三年成熟后也生母牛，一年一只，问N年以后共几头牛

F(n) = F(n-1) + F(n-3)

• code
  第一题的解法三

第四课加题

动态规划求解

技巧：使用map的lower_bound求大于等于目标值的第一个指，这里需要得到小于等于某值得第一个值，就需要加上负号

• 思路
  要想获得得money最大，肯定选取能力范围内money最大得工作；而且同样得money肯定选取hard小得工作，所以需要预处理工作数组；

1）将所有的工作存入哈希表，按找难度从易到难，相同难度回报由高到底，从堆顶排到堆底；；
2）将所有的工作根据money和hard放进小根堆；遍历所有的工作，工作降采样，将每种难度回报最大的工作储存，并将难度大，回报小的工作舍弃；
3) 选择满组自身体力的第一份工作就是所求

• code

#include
#include
#include
#include