动态规划：
要点：
- 找到动态转移方程
- 找到base case 初始条件
优化方向：空间优化，关注前两个值即可，用两个变量代替。
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
public static int coinChange2(int[] coins, int amount) {
//参数判断
if (coins.length <= 0) {
return -1;
}
//dp数组:存储amount从0到11时需要的硬币数量
int[] memo = new int[amount + 1];
//base case 0元时值为0
memo[0] = 0;
//遍历从amount = 1开始遍历，结果放入dp数组
for (int i = 1; i <= amount; i++) {
//遍历 amount 减去已有的不同数值时 读取dp存储的需要的硬币数量
int min = Integer.MAX_VALUE;
for (int coin : coins) {
//减去coin的值剩余钱数
int left = i - coin;
if (left >= 0 && memo[left] < min) {
//需要的数量为存储数量+ 1（当前数值硬币）
min = memo[left] + 1;
}
}
memo[i] = min;
}
return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
}
使用最小花费爬楼梯
给你一个整数数组 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 。
public int minCostClimbingStairs2(int[] cost) {
int size = cost.length;
//dp
int[] dp = new int[size];
//base case
dp[0] = 0;
dp[1] = Math.min(cost[0], cost[1]);
for (int i = 2; i < size; i++) {
dp[i] = Math.min(dp[i-2] + cost[i-1], dp[i-1] + cost[i]);
}
return dp[size-1];
}
连续天数的最高销售额
某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。要求实现时间复杂度为 O(n) 的算法。
示例 1:
输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
示例 2:
输入：sales = [5,4,-1,7,8]
输出：23
解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。
/**
* 动态规划解析：
* 状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 sales[i] 为结尾的连续子数组最大和。
* 转移方程： 若 dp[i−1]≤0，说明 dp[i−1] 对 dp[i] 产生负贡献，
* 即 dp[i−1]+sales[i]还不如 sales[i]本身大。
* <p>
* dp[i] = dp[i−1] + sales[i], dp[i−1]>0
* dp[i] = sales[i], dp[i−1]≤0
* 初始状态： dp[0]=sales[0]，即以 sales[0] 结尾的连续子数组最大和为 sales[0]
* 返回值： 返回 dp 列表中的最大值，代表全局最大值。
* 空间优化：
* 由于 dp[i]只与 dp[i−1] 和 sales[i] 有关系，因此可以将原数组 sales 用作 dp 列表，即直接在 sales上修改即可。
* 由于省去 dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1)。
* [5,4,-1,7,8]
* [0,5,9,8,15,23]
* [-2,1,-3,4,-1,2,1,-5,4]
* [0,]
*/
public static int maxSales(int[] sales) {
//初始状态
int res = sales[0];
for (int i = 1; i < sales.length; i++) {
//状态转移方程
//dp[i] = dp[i−1] + sales[i], dp[i−1]>0
//dp[i] = sales[i], dp[i−1]≤0
int max = Math.max(sales[i - 1], 0);
sales[i] += max;
res = Math.max(res, sales[i]);
}
return res;
}
连续数列
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
public int maxSubArray(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
int max = Math.max(nums[i - 1], 0);
nums[i] = nums[i] + max;
res = Math.max(nums[i], res);
}
return res;
}
按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间， 因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
/**
* dp[i][0] 考虑前i个预约，第i个预约不接的最长预约时间
* dp[i][1] 考虑前i个预约，第i个预约接的最长预约时间
* 从前往后计算，已计算出前i-1个dp值，考虑计算dp[i][0/1]的答案
* 转移方程
* dp[i][0] 第i个状态不接， 第i-1个预约接不接都可以，考虑dp[i-1][0] 和dp[i-1][1] 两个状态转移过来 dp[i][0] = max(dp[i-1][0],dp[i-1][1])
* dp[i][1] 第i个状态接， 第i-1个预约不接，从dp[i-1][0]状态转移 转移方程：dp[i][1] = dp[i-1][0] + numsi (numsi表示第i个预约的时长)
* 答案取 max(dp[n][0], dp[n][1]) ,n表示预约的个数
*
* 优化：计算dp[i][0/1] 时，只与前一个状态dp[i-1][0/1]有关，可以不用开数组，只用两个变量dp0和dp1 分别存储dp[i-1][0] 和dp[i-1][1]
*
* */
public static int massage(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
//两个变量,分别存储dp[i-1][0] 和dp[i-1][1]
int dp0 = 0, dp1 = nums[0];
for (int i = 1; i < n; ++i){
//计算第i个不接的情况，考虑i-1接与不接两种情况
int tdp0 = Math.max(dp0, dp1); // 计算 dp[i][0]
//计算第i个接的情况，第i-1个只能不接
int tdp1 = dp0 + nums[i]; // 计算 dp[i][1]
dp0 = tdp0; // 用 dp[i][0] 更新 dp_0
dp1 = tdp1; // 用 dp[i][1] 更新 dp_1
}
return Math.max(dp0, dp1);
}
三步问题
有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3
输出：4
说明: 有四种走法
示例2:
输入：n = 5
输出：13
提示:
n范围在[1, 1000000]之间
三种情况：
（1）剩余一层楼梯要走然后一步走一层
（2）剩余两层楼梯要走，然后一步走两层
（3）剩余三层楼梯要走，然后一步走三层
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
public int waysToStep(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i < n+1; i++) {
dp[i] = (dp[i-1] + (dp[i-2] + dp[i-3]) % 1000000007) % 1000000007;
}
return dp[n];
}
跳跃训练
今天的有氧运动训练内容是在一个长条形的平台上跳跃。台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 5
输出：8
public int trainWays(int num) {
if(num == 0){
return 0;
}
if (num <=2) {
return num;
}
int[] dp = new int[num + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < num + 1; i++) {
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
return dp[num];
}
