24点问题

24点 Lintcode 739

已知：

给定四个1-9的数字，使用运算符加减乘除和括号，使得运算结果为24. 求结果为24的可能性. 

示例:

4, 1, 8, 7   => 8 * （7 - 4） * 1 = 24     true
1, 1, 1, 2                                false
3, 3, 8, 8   => 8 / ( 3 - 8 / 3) = 24     true

思路：

典型的动态规划问题，以4，1，8，7为例，要使得结果为24，只要计算数组为1，8，7获得4-24，24-4，24+4，24/4 , 4/24 , 4*24的可能性即可，只要满足一个为true，结果就为true.
但是会不会存在**无法递推**的情况呢？我认为是有的，比如说 A*B - C*D 的情况，就是无法递推的，因此需要独立讨论，不过该题目中即使没考虑这种情况也是通过的，比如说5，5，9，9，应该为true，但我的代码是false仍然通过了(惭愧惭愧).

综上，代码如下：

public boolean compute24(double[] nums) {
        //如果是A*B+C*D类型
        if (ABtoCD(nums)) {
            return true;
        }
        return calculate(nums, 24);
    }

    private boolean ABtoCD(double[] nums) {
        double[][] numss = { { nums[0], nums[1], nums[2], nums[3] },
                { nums[0], nums[2], nums[1], nums[3] },
                { nums[0], nums[3], nums[1], nums[2] },
                { nums[1], nums[2], nums[0], nums[3] },
                { nums[1], nums[3], nums[0], nums[2] },
                { nums[2], nums[3], nums[0], nums[1] } };

        //A$B 代表 B/A，只是一个标识用的符号
        char[][] css = { { '*', '/', '$' }, { '+', '-' }, { '*', '/', '$' } };
        for (int i = 0; i < numss.length; i++) {
            double temp1 = 0, temp2 = 0;
            for (int j = 0; j < css[0].length; j++) {
                for (int k = 0; k < css[1].length; k++) {
                    for (int l = 0; l < css[2].length; l++) {
                        switch (css[0][j]) {
                        case '*':
                            temp1 = numss[i][0] * numss[i][1];
                            break;
                        case '/':
                            temp1 = numss[i][0] / numss[i][1];
                            break;
                        case '$':
                            temp1 = numss[i][1] / numss[i][0];
                            break;
                        }
                        switch (css[2][l]) {
                        case '*':
                            temp2 = numss[i][2] * numss[i][3];
                            break;
                        case '/':
                            temp2 = numss[i][2] / numss[i][3];
                            break;
                        case '$':
                            temp2 = numss[i][3] / numss[i][2];
                            break;
                        }
                        if (css[1][k] == '+' && temp1 + temp2 == 24) {
                            return true;
                        }
                        if (css[1][k] == '-' && temp1 - temp2 == 24) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    private boolean calculate(double[] nums, double value) {
        if (nums.length == 1) {
            return nums[0] - value <= 0.00001 && value - nums[0] <= 0.00001;
        }

        double[] minorNums = new double[nums.length - 1];
        for (int i = 0; i < nums.length; i++) {
            int index = 0;
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                minorNums[index++] = nums[j];
            }

            if (calculate(minorNums, value - nums[i])
                    || calculate(minorNums, value + nums[i])
                    || calculate(minorNums, value * nums[i])
                    || calculate(minorNums, value / nums[i])
                    || calculate(minorNums, nums[i] / value)
                    || calculate(minorNums, nums[i] - value)) {
                return true;
            }
        }

        return false;
    }

这里请读者思考下，为什么ABtoCD中判断是结果是否为24，而calculate中判断是nums[0] 和 value差值不超过0.00001呢？
~(@^_^@)~希望对您有所帮助