[每日一题]LintCode1861 老鼠跳跃

忽略奇数偶数步，忽略胶水，就是一个一维dp，例如只能走1 2 4步，dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 4] （当然要注意最后的台阶要单独处理  因为可以到负的层次）

加上奇数偶数步，那就是一个二维dp, dp[0][j]表示偶数步到i层，dp[1][i]表示奇数步到i层

初始化dp为0，dp[0][0] = 1，注意dp[1][0]是不为1的，因为第一步只能是奇数步

加上胶水的条件，只需要判断当前台阶是否有胶水，如果有continue，即可这样到这个台阶的走法为0，也对后来的台阶没有影响

最后在加上MOD的条件，即可。

class Solution {
public:
    /**
     * @param arr: the steps whether have glue
     * @return: the sum of the answers
     */
    const long long MOD = 1e9 + 7;
    long long dp[2][50010];
    int ratJump(vector<int> &arr) {
        // Write your code here.
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
      //  cout << MOD << endl;
        int n = arr.size();
        for(int i = 1; i < n - 1; i++)
        {
            if(arr[i]) continue;
            dp[0][i] = (dp[0][i] + dp[1][i - 1]) % MOD;
            dp[1][i] = (dp[1][i] + dp[0][i - 1]) % MOD;
            if(i >= 2) dp[1][i] = (dp[1][i] + dp[0][i - 2]) % MOD;
            if(i >= 3) dp[0][i] = (dp[0][i] + dp[1][i - 3]) % MOD;
            if(i >= 4) dp[0][i] = (dp[0][i] + dp[1][i - 4]) % MOD, dp[1][i] = (dp[1][i] + dp[0][i - 4]) % MOD;
        }
        dp[0][n - 1] = (dp[0][n - 1] + ((dp[1][n - 1 - 1] + dp[1][n - 1 - 1]) % MOD + dp[1][n - 1 - 1]) % MOD) % MOD;
        dp[1][n - 1] = (dp[1][n - 1] + ((dp[0][n - 1 - 1] + dp[0][n - 1 - 1]) % MOD + dp[0][n - 1 - 1]) % MOD) % MOD;
        if(n - 1 >= 2)
            dp[1][n - 1] = (dp[1][n - 1] + dp[0][n - 1 - 2] * 2 % MOD) % MOD, dp[0][n - 1] = (dp[0][n - 1] + dp[1][n - 1 - 2] * 2 % MOD) % MOD;
        if(n -  1 >= 3) dp[0][n - 1] = (dp[0][n - 1] + dp[1][n - 1 - 3] * 2 % MOD) % MOD, dp[1][n - 1] = (dp[1][n - 1] + dp[0][n - 1 - 3]) % MOD; 
        if(n - 1 >= 4) dp[0][n - 1] = (dp[0][n - 1] + dp[1][n - 1 - 4]) % MOD, dp[1][n - 1] = (dp[1][n - 1] + dp[0][n - 1 - 4]) % MOD;
        return (dp[0][n - 1] + dp[1][n - 1]) % MOD; 
    }
};