这题也算是比较基础的DP了，思路就是将从上往下的过程反过来，定义为当上一步为（奇/偶）步到达i台阶时的走法。这样很容易推出来，同样的奇数步也一样。递推方程简单，主要处理的难点就是要考虑到这个逆推的过程，因为考虑到低于0层也要统计，用下标记录的话显然不合适自顶而下的递推，而自下而上的方式只需要在结束后统计一下n-1到n-1+4的方式即可。
int ratJump(vector<int> &arr) {
// Write your code here.
const int mod = 1e9+7;
int len = arr.size();
int dp[len+5][2];
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
int odd[3] = {1,2,4};
int even[3] = {1,3,4};
for(int i = 0 ; i < len-1 ; i ++){
for(int j = 0 ; j < 3 ; j ++){
if(arr[i+odd[j]]==0||i+odd[j]>=len){
dp[i+odd[j]][1] += dp[i][0];
dp[i+odd[j]][1]%=mod;
}
if(arr[i+even[j]]==0||i+even[j]>=len){
dp[i+even[j]][0] += dp[i][1];
dp[i+even[j]][0] %= mod;
}
}
}
int ans = 0;
for(int i = len-1 ; i<len+4 ; i ++ ){
ans = (ans + dp[i][1] +dp[i][0])%mod;
}
return ans;
}