动态规划的基础知识

https://blog.csdn.net/misayaaaaa/article/details/72153061

LeetCode  70

解法一：循环

手画到n=6的情况，发现f(1)+f(2)=f(3),就是n=1时是1，n=2时是2，n=3时是3，n=4时是5，n=5时是8，n=6时是13.

到达第i阶有多少种爬法，只与第i-1阶、第i-2阶的爬法数量有关

class Solution {  
public:  
     int climbStairs(int n) {  
        int prev = 0;  
        int cur = 1;  
        for(int i = 1; i <= n ; ++i){  
            int tmp = cur;  
            cur = prev + cur;  
            prev = tmp;  
        }  
        return cur;  
    }  
};  

解法二：矩阵快速幂法求解

(a*b)%c=(a%c)*(b%c)%c

基础知识详解见博客：https://blog.csdn.net/ltyqljhwcm/article/details/53043646

以下代码来自博客： https://blog.csdn.net/linwh8/article/details/77894642

#include "stdafx.h"
#include<iostream>
# include <cstring>
using namespace std;
//typedef　int　size;  size a = 5; //相当于int a = 5 
//这里的意思就是定义longlong类型的别名类ll
typedef long long ll;

// 定义矩阵
struct Matrix {
	ll m[2][2];
};

// 矩阵幂的底
/* [0,1]
   [1,1]   */
Matrix base = { 0, 1, 1, 1 };

// 矩阵乘法
Matrix multi(const Matrix& A, const Matrix&B) {
	Matrix result;
	//初始化二维数组result的值为0，memset函数在socket中多用于清空数组
	//memset()函数原型是extern void *memset(void *buffer, int c, int count)
	//buffer：为指针或是数组,    c：是赋给buffer的值,    count：是buffer的长度.
	memset(result.m, 0, sizeof(result));
	//二维矩阵乘法的表示
	//result.m[0][0] = A.m[0][0] * B.m[0][0]+A.m[0][1] * B.m[1][0];
	//result.m[0][1] = A.m[0][0] * B.m[0][1]+A.m[0][1] * B.m[1][1];
	//result.m[1][0] = A.m[1][0] * B.m[0][0]+A.m[1][1] * B.m[1][0];
	//result.m[1][1] = A.m[1][0] * B.m[0][1]+A.m[1][1] * B.m[1][1];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				result.m[i][j] += A.m[i][k] * B.m[k][j];
			}
		}
	}
	return result;
}

// 矩阵的N次方，矩阵快速幂的核心
Matrix power(int N) {
	Matrix result = { 1, 0, 0, 1 };
	while (N) {
		//当N的二进制位最低位（最右侧的那个数）为0时
		if (N & 1) {
			//获取矩阵乘法的结果
			result = multi(result, base);			
		}
		base = multi(base, base);
		//右移，相当于每次除以2.用二进制看，就是我们不断遍历N的二进制位
		N >>= 1;
	}
	return result;
}

// 计算，调用子函数
ll calcu(int N) {
	if (N == 0) return 0;
	int e = N - 1;
	Matrix p = power(e);
	ll result = p.m[1][0] * 0 + p.m[1][1] * 1;
	return result;
}

// 主函数
int main(void) {
	int N;
	cin >> N;

	ll result;
	result = calcu(N);

	cout << "The result is " << result << endl;
	return 0;
}

LeetCode 198

最后一家要不要打劫，完全取决于前一家有没有被打劫。嗯，还要打劫的金额最高。

解法一：动态规划

#include "stdafx.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

//动态规划
int rob(vector<int>& nums) {
	int len = nums.size();
	if (len == 0) return 0;
	if (len == 1) return nums[0];
	vector<int> mmax;
	mmax.push_back(nums[0]);
	//max()包含在c++标准库中头文件<algorithm>中
	mmax.push_back(max(nums[0], nums[1]));
	for (int i = 2; i<len; i++) {
		mmax.push_back(max(nums[i] + mmax[i - 2], mmax[i - 1]));
	}
	return mmax[len - 1];
}

int main()
{
	vector<int>nums = {5,6,1,2,3,7};
	int answer = rob(nums);
    return 0;
}

解法二：贪心算法。。。嗯，贪心算法不一定能获取最优解，这个方法GG了

贪心算法的基础讲解：http://babybandf.blog.163.com/blog/static/61993532010112923767/

贴上自己半成品的代码吧，红红火火恍恍惚惚

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//函数声明
void sort_element(vector<int>& nums, vector<int>& index, int begin, int end);

//贪心算法
int rob(vector<int>& nums) {
	int len = nums.size(),answer=0;
	if (len == 0) return 0;
	if (len == 1) return nums[0];

	//建立数组，存储nums的值所对应的索引位置
	vector<int>index;
	//初始化index
	for (int i = 0; i < nums.size(); i++) {
		index.push_back(i);
	}
	//手写快排（因为快排不稳定，直接调用，我怕跟索引位置对不上），将nums中的值按照从大到小的顺序排序
	sort_element(nums, index, 0, nums.size()-1);

	//贪心算法，先尽可能取大的，判断索引位置不挨着就存
	//考虑到如果存在连续的最大值，由于快排不稳定，选取这两个最大值两侧的哪一个值成为了问题
	for (int i = 0; i < nums.size(); i++) {
		
	}

	return  answer;
}

void sort_element(vector<int>& nums, vector<int>& index, int begin, int end) {	

	if (begin < end) {
		int middle = (begin + end) / 2;
		int i = begin - 1, j = end + 1;

		while (true) {

			while (nums[++i] > nums[middle]);
			while (nums[--j] < nums[middle]);
			if (i >= j)  break;
			//随手一写，本想顶一个宏的，algorithm里面居然有这个函数，那就直接用好了
			swap(nums[i], nums[j]);
			swap(index[i], index[j]);
		}
		sort_element(nums, index, begin, i-1);
		sort_element(nums, index, j+1, end);
	}


}

int main()
{
	vector<int>nums = { 5,6,1,2,3,7 };
	int answer = rob(nums);
    return 0;
}

LeetCode 53

解法一：动态规划

#include "stdafx.h"
#include<iostream>
#include<algorithm>
#include<vector>

int maxSubArray(std::vector<int>& nums) {
	if (nums.empty()) return 0;
	int result = nums[0], f = 0;
	for (auto i = 0; i < nums.size(); i++) { 
		f = std::max(f + nums[i], nums[i]);
		//不断更新当前最优解 
		result = std::max(result, f);
	}
	return result;
}

int main()
{
	std::vector<int> nums = { -2, 1,-3, 4,-1, 2, 1,-5, 4 };
	maxSubArray(nums);
    return 0;
}

解法二：分治算法