746、数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
dp[i] = min(dp[i-1],dp[i-2])+cost[i]
// dp[i]:到第i个阶梯最小花费值
// 状态转移：1）从i-1阶梯爬1步，2）从i-2阶梯爬2步
// dp[i] = min(dp[i-1],dp[i-2])+cost[i]
vector<int> dp;
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();dp.resize(n, 0);dp[0] = cost[0];dp[1] = cost[1];for(int i = 2; i < n; i++)dp[i] = min(dp[i-1], dp[i-2]) + cost[i];return min(dp[n-1], dp[n-2]);}
};
结果：
执行用时：12 ms, 在所有 C++ 提交中击败了64.35% 的用户
内存消耗：13.6 MB, 在所有 C++ 提交中击败了34.69% 的用户
1025、爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
- 选出任一 x，满足 0 < x < N 且 N % x == 0 。
- 用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
N=1 的时候，区间 (0,1)中没有整数是 n 的因数，所以此时 Alice 败。
N=2 的时候，Alice 只能拿 1，N 变成 1，Bob 无法继续操作，故 Alice 胜。
N=3 的时候，Alice 只能拿 1，N 变成 2，根据 N=2的结论，我们知道此时 Bob 会获胜，Alice 败。
N=4 的时候，Alice 能拿 1 或 2，如果 Alice 拿 1，根据 N=3 的结论，Bob 会失败，Alice 会获胜。
N=5 的时候，Alice 只能拿 1，根据 N=4的结论，Alice 会失败。
===》NNN 为奇数的时候 Alice（先手）必败，NNN 为偶数的时候 Alice 必胜
class Solution {
public:bool divisorGame(int N) {return N % 2 == 0;}
};
结果：
执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了61.86% 的用户
面试题0801、三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3
输出：4
说明: 有四种走法示例2:
输入：n = 5
输出：13
dp[i] = dp[i-1] % MOD + dp[i-2] % MOD + dp[i-3] % MOD;
typedef long long ll;
class Solution {
public:ll MOD = 1e9+7;vector<ll> dp;int waysToStep(int n) {if(n > 3) dp.resize(n + 1,0);else dp.resize(4);dp[1] = 1;dp[2] = 2;dp[3] = 4;for(int i = 4; i <= n; i++){dp[i] = dp[i-1] % MOD + dp[i-2] % MOD + dp[i-3] % MOD;}return dp[n] % MOD;}
};
结果：
执行用时：104 ms, 在所有 C++ 提交中击败了5.60% 的用户
内存消耗：22.4 MB, 在所有 C++ 提交中击败了13.33% 的用户