又见台阶——交替记录奇数前缀和与偶数前缀和

设f[i]表示0跳到i的方法数，显然有

1. 若i是积水，f[i]=0;
2. 若i为偶数，则i是由奇数跳转过来，有f[i] = sum(f[k]) (k为小于i的奇数)
3. 若n为奇数，则n是由偶数跳转过来，有f[i] = sum(f[k]) (k为小于i的偶数)
   由于每次计算都只涉及奇数和与偶数和，那我们完全没必要在开数组。
   只需从1到n扫描一遍，记录并更新当前的奇数和sum1、偶数和sum2 即可。

另外值得注意的是，初始时应设置sum1=0、sum2=1。
送上AC代码：

import java.util.*;


public class Solution {
    /**
     * 又见台阶
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    int mod = (int)(1e9+7);
    public int solve (int n, int m, int[] a) {
        // write code here
        boolean[] tag = new boolean[n+1];
        for(int i=0;i<m;i++){
            tag[a[i]]=true;
        }
        long sum1=0,sum2=1;//奇数和，偶数和
        for(int i=1;i<=n;i++){
            if(tag[i])continue;
            if(i%2==0){
                sum2 += sum1;//sum1为当前的f[i]的值
                sum2 %= mod;
            }
            else{
                sum1 += sum2;//sum2为当前的f[i]的值
                sum1 %= mod;
            }
        }
        if(n%2==0)return tag[n]?0:(int)sum1;
        else return tag[n]?0:(int)sum2;
    }
}