题解 | #杨辉三角的变形#

感觉这题的执行提交输入1000导致堆溢出就是用来恶心人的。杨辉三角很显然的动态规划问题，解题思路就应该往上靠。结果搞成纯粹的找规律题目。有点想笑。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            //getEvenNumber(n);
            getEvenNumber2(n);
        }
    }

    public static void getEvenNumber2(int num) {
        if (num == 1 || num == 2) {
            System.out.println(-1);
        } else if (num % 4 == 3 || num % 4 == 1) {
            System.out.println(2);
        } else if (num % 4 == 0) {
            System.out.println(3);
        } else if (num % 4 == 2) {
            System.out.println(4);
        } else {
            System.out.println(-1);
        }
    }

    public static void getEvenNumber(int n) {

        int res = -1;
        if (n == 1) {
            System.out.println(res);
            return;
        }
        // 定义一个dp数组
        int[][] dp = new int[n][2 * n - 1];
        // 为了少几个判断，初始化前两行
        dp[0][0] = 1;
        dp[1][0] = 1;
        dp[1][1] = 1;
        dp[1][2] = 1;
        // 初始化dp数组
        for (int i = 2; i < n; i++) {
            for (int j = 0; j < 2 * i + 1; j++) {
                // 将杨辉三角最外层初始化为1
                if (j == 0 || j == 2 * i) {
                    dp[i][j] = 1;
                } else {
                    if (j == 1) {
                        // j=1即 当前值只能由上一行的左边两个得到
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    } else if (j == 2 * i - 1) {
                        // j=2i-1表示当前值只能上一行右边两个值得到
                        dp[i][j] = dp[i - 1][j - 2] + dp[i - 1][j - 1];
                    } else {
                        // 当前值由三个值得到
                        dp[i][j] = dp[i - 1][j - 2] + dp[i - 1][j - 1] + dp[i - 1][j];
                    }
                }
            }
        }
        // 查询第i行的dp[i-1][j]的第一个值为偶数时的值
        for (int j = 0; j < 2 * n - 1; j++) {
            if (dp[n - 1][j] % 2 == 0) {
                res = j + 1;
                break;
            }
        }
        System.out.println(res);
    }
}