Java dp不压缩

每个位置有两个状态， 拿或者不拿

• 拿当前位置时， 最大值只能从 不拿上一个位置 转移来
• 不拿当前位置时，最大值可以从 不拿上一个位置 和 拿上一个位置 转移

写出dp：

    public long subsequence (int n, int[] array) {

        long[][] dp = new long[2][n+5];
        dp[0][0]=array[0];
        dp[1][0]=0;
        dp[0][1]=array[1];
        dp[1][1]=dp[0][0];
        for(int i=2;i<array.length;++i){
            dp[0][i] = dp[1][i-1]+array[i];
            dp[1][i]=Math.max(dp[1][i-1],dp[0][i-1]);
        }
        return Math.max(dp[1][n-1],dp[0][n-1]);
    }

观察到每次转移只依赖上一个位置， 所以可以做状态压缩