leetcode day8 动态规划篇 3259+746+198
3259超级饮料的强化能量
来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。
返回在接下来的 n 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。
示例 1：
输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：
要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。
示例 2：
输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
输出：7
解释：
第一个小时饮用能量饮料 A。
切换到能量饮料 B ，在第二个小时无法获得强化能量。
第三个小时饮用能量饮料 B ，并获得强化能量。
解题思路：动态规划问题，i小时获取的总能量与前面的状态有关。创建一个二维数组存储总能量，dp[i][0]表示第i小时从A获得能量，dp[i][1]表示第i小时从B获得能量。
特殊情况，当i=1或者i=2时，获取最大能量一定是没有切换过的。
i从1开始，所以后面加的是A[i-1]
（1）未切换，dp[i][0]=dp[i-1][0]+A[i-1]
dp[i][1]=dp[i-1][1]+A[i-1]
（2）切换，从前两步开始加，因为切换到能量饮料 ，在第二个小时无法获得强化能量。
与未切换的比大小，选出最大值即可。
dp[i][0]=max(dp[i][0],dp[i-2][1]+A[i-1])
dp[i][1]=max(dp[i][1],dp[i-2][0]+B[i-1])
long long max(long long a,long long b){
if(a>b)return a;
else return b;
}
long long maxEnergyBoost(int* energyDrinkA, int energyDrinkASize, int* energyDrinkB, int energyDrinkBSize) {
int n=energyDrinkASize;
//dp[i][0]第i小时取A，dp[i][1]第i小时取B
long long dp[n+1][3]={};
for(int i=1;i<=n;i++){
dp[i][0]=dp[i-1][0]+energyDrinkA[i-1];
dp[i][1]=dp[i-1][1]+energyDrinkB[i-1];
if(i>2){
dp[i][0]=max(dp[i][0],dp[i-2][1]+energyDrinkA[i-1]);
dp[i][1]=max(dp[i][1],dp[i-2][0]+energyDrinkB[i-1]);
}
}
return max(dp[n][0],dp[n][1]);
}746 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
解题思路：cost数组个数为n,楼梯顶部为第n个台阶
dp[i][0]表示从下标0开始爬到第i个台阶
dp[i][1]表示从下标1开始爬到第i个台阶
到达第i个台阶有两种方法
（1）从0开始爬上去，到达第i个台阶可以从i-1或者是i-2个台阶爬上去。从i-1爬上去，加上cost[i-1]的花费。从i-2爬上去，加上cost[i-2]的花费，
dp[i][0]=min(dp[i-1][0]+cost[i-1],dp[i-2][0]+cost[i-2]);
（2）从1开始爬上去，与（1）同理
dp[i][1]=min(dp[i-1][1]+cost[i-1],dp[i-2][1]+cost[i-2]);
int min(int a,int b){
if(a>b)return b;
else return a;
}
int minCostClimbingStairs(int* cost, int costSize) {
int n=costSize;
//顶部台阶为n
//dp[i][0]从下标0开始到达第i个台阶
int dp[n+1][3]={};
dp[1][0]=cost[0];
for(int i=2;i<=n;i++){
dp[i][0]=min(dp[i-1][0]+cost[i-1],dp[i-2][0]+cost[i-2]);
dp[i][1]=min(dp[i-1][1]+cost[i-1],dp[i-2][1]+cost[i-2]);
}
return min(dp[n][0],dp[n][1]);
}198 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
偷第i个房间获取的总金额与前面的状态有关，考虑动态规划求解。
方法一
状态转移方程：
i小于2时 dp[i]=nums[i];
i等于2时 dp[i]=dp[0]+nums[2];
i大于2时 dp[i]=Max(dp[i-2]+nums[i],dp[i-3]+nums[i]);
为什么i大于2要考虑前两位和前三位的数呢？
举个例子 数组 2 1 1 2 取第一个和第四个可获得最大值。
int Max(int a,int b){
if(a>b)return a;
else return b;
}
int rob(int* nums, int numsSize) {
int n=numsSize,max=0;
int dp[n+1]={};
for(int i=0;i<n;i++){
if(i<2)dp[i]=nums[i];
else if(i==2)dp[i]=dp[0]+nums[2];
else dp[i]=Max(dp[i-2]+nums[i],dp[i-3]+nums[i]);
if(dp[i]>max)max=dp[i];
}
return max;
}方法2
分第i间房偷和不偷的情况。
(1)偷 dp[i]=dp[i-2]+nums[i]
(2)不偷第i间房，偷第i-1间房，dp[i]=dp[i-1]
两种情况比较即可
int Max(int a,int b){
if(a>b)return a;
else return b;
}
int rob(int* nums, int numsSize) {
int n=numsSize;
int dp[n+1]={};
for(int i=0;i<n;i++){
if(i==0)dp[0]=nums[0];
else if(i==1)dp[1]=Max(nums[0],nums[1]);
else dp[i]=Max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}