1、斐波那契數列優化

使用滾動變量，保存當前計算結果和前兩項值

(1)R=A+B

(2)更新計算對象，A=B，B=R

#include<iostream>
using namespace std;int fun(int n)
{if (n == 0)return 0;if (n == 1 || n == 2)return 1;int num1=1;int num2=1;int sum=0;int i = 3;while (i<= n){sum = num1 + num2;num1 = num2;num2 = sum;//cout << sum << endl;i++;}return sum;
}int main()
{cout<<fun(10);return 0;
}

?2、防止越界方法

1e9+7——int范圍內最大的素數——1000000007

F(51)=F(49)%(1e9+7)+F(50)%(1e9+7)

3、青蛙爬樓梯

一只青蛙，一次可以爬一級樓梯，也可以爬兩級，求n級臺階有多少種跳法

1級：1次1級

2級：1次1級? 1次1級

?????? ? 1次2級

3級：1次1級? 2級的情況

???????? 1次2級? 1級的情況

F(n)=F(n-1)+F(n-2)??????????????? F(1)=1??????? F(2)=2

4、分治法

把大的問題分解為若干個解決方案完全相同的子問題

1、問題難度隨數據規模增加而減小

2、問題可分

3、子問題的解可合并

4、子問題的解相互獨立

二分查找

第一種方法

#include<iostream>
#include<vector>
using namespace std;int BinargChop(vector<int>&nums,int target)
{int left = 0;int right = nums.size()-1;int middle=0;while (left<right){middle = (left + right) / 2;if (nums[middle] < target){left = middle+1;}else if (nums[middle] > target){right = middle-1;}if (nums[middle] == target){return middle;}}}int main()
{vector<int>nums = { 1,12,36,56,88,99 };int target = 88;cout << BinargChop(nums, target);
}

第二種方法

#include<iostream>
#include<vector>
using namespace std;int BinargChop(vector<int>& nums, int target,int left,int right)
{int middle = 0;while (left < right){middle = (left + right) / 2;if (nums[middle] < target){left = middle + 1;BinargChop(nums, target, left, right);}else if (nums[middle] > target){right = middle - 1;BinargChop(nums, target, left, right);}if (nums[middle] == target){return middle;}}
}int main()
{vector<int>nums = { 1,12,36,56,88,99 };int target = 99;int left = 0;int right = nums.size()-1;cout << BinargChop(nums, target,left,right);
}