C++动态规划 DP

动态规划把大问题拆成小问题，把小问题算出来用dp数组存起来，大问题用小问题解决，递推，不用重复算。

1、斐波那契数列

题目大意：1 1 2 3 5 8 13 21 34 …

公式：dp[n]=dp[n-1]+dp[n-2]

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;//找第n位元素是什么，从1开始
	int dp[100];
	//设初始条件
	dp[1]=1;
	dp[2]=1;
	//递推
	for(int i=3;i<=n;i++){
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[n];//第n位元素的数字
	return 0;
}

2、爬楼梯

题目大意：一次爬1阶，或者2阶，爬到n阶有几种方法

1 2 3 5 8 13 21 34…

公式：dp[n]=dp[n-1]+dp[n-2]

 #include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int dp[105];
	dp[1]=1;
	dp[2]=2;
	for(int i=3;i<=n;i++){
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[n];
	return 0;
}

3、打家劫舍

题目大意：一排房子，每间房子有固定钱财。不能偷相邻两间房子，求最多能偷多少钱。

定义dp, dp[i]：前i间房子，能偷到的最大总钱数

只有1间时，只能偷它，dp[1]=a[1]

有两间时：选钱多的那一间，dp[2]=max(a[1],a[2])

到第i间只有两种选择

1、不偷第i间：最大值=dp[i-1]

2、偷第i间：就不能偷i-1间，只能用dp[i-2]+a[i]；

公式：dp[i]=max(dp[i-1],dp[i-2]+a[i])

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[105],dp[105];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	dp[1]=a[1];
	dp[2]=max(a[1],a[2]);
	for(int i=3;i<=n;i++){
		dp[i]=max(dp[i-1],dp[i-2]+a[i]);//在不偷第i间与偷第i间中选一个最大值
	}
	cout<<dp[n];
	return 0;
}