《算法：leetCode刷題》動态規劃

一.動态規劃需要弄清楚的四個方面

1.确認原問題與子問題 2.确認狀态 3.确認邊界狀态的值 4.确定狀态轉移方程。

二.由易入難，做幾道動态規劃的題目

1.爬樓梯問題，每次能爬1級台階或者2級台階，問爬n級台階有多少種爬法？

解題思路：可以采用回溯法也可以采用更高效的動态規劃法

回溯法實作代碼：

#include<iostream>
using namespace std;

class Solution{
	
	public:
		int climbStairs(int n){
			
			if(n==1||n==2){
				return n;
			}
			 
			return climbStairs(n-1)+climbStairs(n-2);
		}
};


int main()
{
	Solution solve;
	cout<<solve.climbStairs(4)<<endl;
	
	return 0;
}
           

動态規劃實作代碼：

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

class Solution{
	
	public:
		int climbStairs(int n){
			
			vector<int>dp(n+3,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()
{
	Solution solve;
	cout<<solve.climbStairs(6)<<endl;
	
	return 0;
}
           

二.有一個盜賊到一個街道裡面偷東西，東西的價值存放在一個數組中，規定不能盜取相鄰兩家的東西，否則就會觸發警報。問盜賊能夠盜取東西的最大價值是多少呢？例如，物體的價值value[4]={1,3,5,7},那麼盜賊能夠盜取的物體最大價值為10=3+7.

解題思路：每件物體要麼被選，要麼不被選。被選的前提是相鄰的物體沒有被選且選後物體價值要為最大。

dp[i]表示前i個物體的最大價值，那麼dp[1]=nums[1], dp[2]=max(dp[1],nums[2]]), dp[3]=max(dp[2],dp[1]+nums[3]])

狀态轉移方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i])

實作代碼：

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

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


int main()
{
	Solution solve;
	
	int a[6]={5,2,6,3,1,7};
	vector<int>b(a,a+6);
	cout<<solve.stealThing(b)<<endl;
	
	return 0;
}