LeetCode 动态规划（一）
A：爬楼梯
题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
题目样例：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
思路：我们用f(x)表示爬到第x级台阶的方案数，因为最后一步只可能跨越一级台阶或者两级台阶，所以有:
f(x)=f(x-1)+f(x-2)
代码如下：
class Solution {
public:int climbStairs(int n) {int dp[100];dp[0]=1;dp[1]=2;for(int i=2;i<n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n-1];}
};
B：买卖股票的最佳时机
题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
题目样例：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。输入：prices = [7,6,4,3,1] 输出：0
提示：
1 <= prices.length <= 1e50 <= prices[i] <= 1e4
思路：暴力直接解法如下，但是会时间超限
class Solution {
public:int maxProfit(vector<int>& prices) { //暴力解法int maxn=0;int l=prices.size();for(int i=0;i<l-1;i++){for(int j=i+1;j<l;j++){if((prices[j]-prices[i])>maxn)maxn=prices[j]-prices[i];}}return maxn;}
};我们采用一次遍历的方法，在遍历的过程中不断更新最小股票价格，如果卖出股票，则利润为卖出股票当日的价格与最小股票价格的差，再不断更新最大利润。
代码如下：
class Solution {
public:int maxProfit(vector<int>& prices) { //一次遍历int minprice=1000000;int maxprofit=0;for(int price:prices){maxprofit=max(price-minprice,maxprofit);minprice=min(price,minprice);}return maxprofit;}};C：最大子序和
题目描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
题目样例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
提示：
1 <= nums.length <= 1e5-1e4 <= nums[i] <= 1e4
思路：对于nums[i]，我们可以考虑nums[i]是单独成为一段还是加入f(i-1)对应的那一段。所以动态转移方程：
f(i)=max{f(i-1)+nums[i],nums[i]}
代码如下：
class Solution {
public:int maxSubArray(vector<int>& nums) {int pre=0;int maxn=nums[0];for(int x:nums){pre=max(x,pre+x);maxn=max(maxn,pre);}return maxn;}
};
D：打家劫舍
题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
题目样例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
思路：对于第k(k>2)间房间，有两种选项
1、偷，那就不能偷第k-1间，总金额为前k-2间房的最高总金额与第k间房金额之和。
2、不偷，总金额为前k-1间房的最大总金额。
由此得到状态转移方程：
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
边界条件：
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
代码如下：
class Solution {
public:int rob(vector<int>& nums) {int l=nums.size();if(!l){return 0;}if(l==1){return nums[0];}int dp[10000];dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<l;i++){dp[i]=max(nums[i]+dp[i-2],dp[i-1]);}return dp[l-1];}
};