public static int countWaysDP(int n) {
        if (n < 0) return 0;
        if (n == 0) return 1;
        if (n == 1) return 2;
        if (n == 2) return 4;

        int[] dp = new int[3];
        dp[0] = 1; dp[1] = 2; dp[2] = 4;
        for (int i = 3; i < n; ++i) {
            dp[i%3] = dp[(i - 1)%3] + dp[(i - 2)%3] + dp[(i - 3)%3];
        }
        return dp[(n - 1)%3];
    }