975. Odd Even Jump

https://leetcode.com/problems/odd-even-jump/description/

从任何一点往后蹦，当这一蹦是奇数次蹦时就蹦到它后面第一个大于等于它的元素；否则就蹦到它后面第一个小于等于它的元素。问最后有几个点开始蹦能蹦到最后一个元素。问有多少种蹦法是用DP/Greedy。action分别为odd跳和even跳，受限于前面点even和odd跳是否成功，因此状态有对应even和odd两种。这道题要倒着遍历，一方面和Dungeon game一样限制来自于终点，最后一个点能否成功取决于它前面点能否成功；另一方面要找到底跳那个，即i点后面第一个大于等于/小于i的数要用到tree map，存后面所在的数，lower_bound即第一个大于等于它的，upper_bound为第一个大于它的，它的前一个即第一个小于等于它的。

代码参考花花。

/*
 * @lc app=leetcode id=975 lang=cpp
 *
 * [975] Odd Even Jump
 *
 * https://leetcode.com/problems/odd-even-jump/description/
 *
 * algorithms
 * Hard (46.06%)
 * Likes:    409
 * Dislikes: 120
 * Total Accepted:    17.2K
 * Total Submissions: 37.4K
 * Testcase Example:  '[10,13,12,14,15]'
 *
 * You are given an integer array A.  From some starting index, you can make a
 * series of jumps.  The (1st, 3rd, 5th, ...) jumps in the series are called
 * odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are
 * called even numbered jumps.
 * 
 * You may from index i jump forward to index j (with i < j) in the following
 * way:
 * 
 * 
 * During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j
 * such that A[i] <= A[j] and A[j] is the smallest possible value.  If there
 * are multiple such indexes j, you can only jump to the smallest such index
 * j.
 * During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j
 * such that A[i] >= A[j] and A[j] is the largest possible value.  If there are
 * multiple such indexes j, you can only jump to the smallest such index j.
 * (It may be the case that for some index i, there are no legal jumps.)
 * 
 * 
 * A starting index is good if, starting from that index, you can reach the end
 * of the array (index A.length - 1) by jumping some number of times (possibly
 * 0 or more than once.)
 * 
 * Return the number of good starting indexes.
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: [10,13,12,14,15]
 * Output: 2
 * Explanation: 
 * From starting index i = 0, we can jump to i = 2 (since A[2] is the smallest
 * among A[1], A[2], A[3], A[4] that is greater or equal to A[0]), then we
 * can't jump any more.
 * From starting index i = 1 and i = 2, we can jump to i = 3, then we can't
 * jump any more.
 * From starting index i = 3, we can jump to i = 4, so we've reached the end.
 * From starting index i = 4, we've reached the end already.
 * In total, there are 2 different starting indexes (i = 3, i = 4) where we can
 * reach the end with some number of jumps.
 * 
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: [2,3,1,1,4]
 * Output: 3
 * Explanation: 
 * From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
 * 
 * During our 1st jump (odd numbered), we first jump to i = 1 because A[1] is
 * the smallest value in (A[1], A[2], A[3], A[4]) that is greater than or equal
 * to A[0].
 * 
 * During our 2nd jump (even numbered), we jump from i = 1 to i = 2 because
 * A[2] is the largest value in (A[2], A[3], A[4]) that is less than or equal
 * to A[1].  A[3] is also the largest value, but 2 is a smaller index, so we
 * can only jump to i = 2 and not i = 3.
 * 
 * During our 3rd jump (odd numbered), we jump from i = 2 to i = 3 because A[3]
 * is the smallest value in (A[3], A[4]) that is greater than or equal to
 * A[2].
 * 
 * We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
 * 
 * In a similar manner, we can deduce that:
 * From starting index i = 1, we jump to i = 4, so we reach the end.
 * From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
 * From starting index i = 3, we jump to i = 4, so we reach the end.
 * From starting index i = 4, we are already at the end.
 * In total, there are 3 different starting indexes (i = 1, i = 3, i = 4) where
 * we can reach the end with some number of jumps.
 * 
 * 
 * 
 * Example 3:
 * 
 * 
 * Input: [5,1,3,4,2]
 * Output: 3
 * Explanation: 
 * We can reach the end from starting indexes 1, 2, and 4.
 * 
 * 
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= A.length <= 20000
 * 0 <= A[i] < 100000
 * 
 */
class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
        const int N = A.size();
        vector<vector<bool>> dp(N, vector<bool>(2));
        map<int, int> m;
        m[A[N - 1]] = N - 1;
        dp[N - 1][0] = dp[N - 1][1] = true;
        int res = 1;
        for (int i = N - 2; i >= 0; --i) {
            // odd, 找第一个A[j] >= A[i]
            // m中key第一个大于等于A[i]的
            auto o = m.lower_bound(A[i]);
            if (o != m.end()) dp[i][0] = dp[o->second][1];
            // even, 找第一个A[j] <= A[i]
            // m中第一个大于A[i]的
            auto e = m.upper_bound(A[i]);
            // 它前面那个即第一个小于等于的
            if (e != m.begin()) dp[i][1] = dp[prev(e)->second][0];
            if (dp[i][0]) ++res;
            m[A[i]] = i;
        }
        return res;
    }
};