博客

一、概述

key point：


1、确定原问题与子问题  2、阶段的状态（包含边界状态（或者说是边界条件））   3、状态转移方程(难点也是最重要的一点)

二、例题1

keypoint


: 如果用递归(本质是压栈和出栈的过程)，提交的时候编译器会报超时，（因为n很大的时候，有很多重复计算）（拆成二叉树理解，比如climbStairs(5）拆成climbStairs(4)+climbStairs(3)，这样1分2,2分4，时间复杂度接近2的n次方），导致运算量过大。

将递归改成迭代后代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
	int climbStairs(int n) {
		if (n == 0 || n == 1 || n == 2) return n;
		vector<int> dp(n+1,0);
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++)
			dp[i] = dp[i - 1] + dp[i - 2];
		return dp[n];
	}

};
int main() {
		int n;
		cin >> n;
		int count = Solution().climbStairs(n);
		cout << "一共有种爬法" << count << endl;
        return 0;
}

例1总结：

例2：

注：

这道题用贪心是不行的

，因为假如我的输入是[5,7,6,3,1],那么如果选择了7那么5,6就不能选(不能选相邻的数，以免触发报警），然后7< 5+6,所以不行

分析后代码如下：

#include<iostream>
#include<vector>
#include<algorithm>	
using namespace std;

class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.size() == 0) return 0;
		if (nums.size() == 1) return nums[0];
		vector<int> dp(nums.size(), 0);
		dp[0] = nums[0];
		dp[1] = max(nums[0], nums[1]);
		for (int i = 2; i < nums.size(); i++)
			dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
		return dp[nums.size() - 1];
	}
};

int main() {
	//测试用例
	vector<int> vect = { 1,2,3,4,5 };
	int result = Solution().rob(vect);
	cout << result;
}

例3：经典动态规划之最大子段和

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
	int maxSubArray(vector<int>&  nums) {
		vector<int> dp(nums.size(), 0);
		dp[0] = nums[0];
		int max_res = dp[0];
		for (int i = 1; i < nums.size(); i++) {
			dp[i] = max(dp[i - 1] + nums[i], nums[i]);
			if(max_res<dp[i]){
				max_res = dp[i];
			}
		}
		return max_res;
	}
};
int main() {
	vector<int> vect = {-1,0,1,2,3,4};
	int res = Solution().maxSubArray(vect);
	cout << res;
}