public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int[][] dp = new int[nums.length][nums.length];
        for (int len = 1; len <= nums.length; ++len) {
            for (int i = 0; i < nums.length - len + 1; ++i) {
                int j = i + len - 1;
                for (int m = i; m <= j; ++m) {
                    int left = i - 1 >= 0 ? nums[i - 1] : 1;
                    int right = j + 1 < nums.length ? nums[j + 1] : 1;
                    int leftDP = m - 1 >= 0 ? dp[i][m - 1] : 0;
                    int rightDP = m + 1 < nums.length ? dp[m + 1][j] : 0;
                    dp[i][j] = Math.max(dp[i][j], leftDP + left * nums[m] * right + rightDP);
                }
            }
        }
        return dp[0][nums.length - 1];
    }