滴滴java双ac代码

这次选择题感觉做的还好，编程题都ac，要是还没面试机会真的ri dog了。。。

状态转移没找出来，全部遍历了，有更好的吗？

package company.didi._20170910._01;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
            }
            int result = process(arr, n);
            System.out.println(result);
        }
    }

    private static int process(int[] arr, int n) {
        int[][] dp = new int[n + 1][n + 1];
        int[][] xor = new int[n + 1][n + 1];
        int i, j;
        for (i = 1; i <= n; ++i) {
            dp[i][i] = arr[i - 1] == 0 ? 1 : 0;
            xor[i][i] = arr[i - 1];
        }
        for (j = 1; j <= n - 1; ++j) {
            for (i = 1; i <= n - j; ++i) {
                dp[i][i + j] = f(arr, dp, xor, i, i + j);
            }
        }
        return dp[1][n];
    }

    private static int f(int[] arr, int[][] dp, int[][] xor, int l, int r) {
        xor[l][r] = xor[l][r - 1] ^ arr[r - 1];
        int max = xor[l][r] == 0 ? 1 : 0;
        for (int i = l; i < r; ++i) {
            max = Math.max(max, dp[l][i] + dp[i + 1][r]);
        }
        return max;
    }

}

leetcode原题。。。

package company.didi._20170910._02;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int result = process(n);
            System.out.println(result);
        }
    }

    private static int process(int n) {
        int[] base = new int[]{2, 3, 5};
        int len = 3;
        int[] index = new int[len];
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i = 1, j, min;
        while (i < n) {
            min = Integer.MAX_VALUE;
            for (j = 0; j < len; j++) {
                min = Math.min(min, ugly[index[j]] * base[j]);
            }
            for (j = 0; j < len; j++) {
                if (min == ugly[index[j]] * base[j]) {
                    ++index[j];
                }
            }
            ugly[i++] = min;
        }
        return ugly[n - 1];
    }

}