京东烽火台编程交流

/**
*做题的时候看题目看乱了，结束后才在牛客网友提示下明白了题目意思，明白意思后第一感觉是动态规划，于是用动态规划试着实现了一下
*思路：利用一个m*m矩阵，m[i][j]表示arr[i] 、arr[j]（即小山i、j能否通信）能否配对，能配对值为1，否则为0
*最后累加矩阵的值除以2得到结果,时间复杂度为O(n^2)
*具体注释如下
*在此感谢左程云老师，关于这方面的知识是在他的公开课上学的
*/
public int getCount(int[] arr) {
	if (arr == null || arr.length < 2) {
		return 0;
	} else {
		int res = 0;
		int[][] dp = getDP(arr);
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {
				res += dp[i][j];
			}
		}
		return res / 2;
	}
}

public int[][] getDP(int[] arr) {
	int[][] dp = new int[arr.length][arr.length];
	dp[0][arr.length - 1] = 1;  //头尾是相邻的，配对
	dp[arr.length - 1][0] = 1;
	for (int i = 0; i < dp.length; i++) {
		for (int j = 0; j < dp.length; j++) {
			if(dp[i][j] == 0){
				if(i == j){
					dp[i][j] = 0;   //自己跟自己不配对
				}else if (i == j - 1 || j == i - 1) {
					dp[i][j] = 1;   //相邻的配对
				} else {
                                        //如果dp[i][j-1]为1，则arr[j-1]满足arr[j - 1] <= Math.min(arr[i], arr[j])使arr[i]、arr[j]配对
					if (j > 0 && dp[i][j - 1] == 1
							&& arr[j - 1] <= Math.min(arr[i], arr[j])) {
							dp[i][j] = 1;
					}
                                        //如果dp[i-1][j]为1，则arr[i-1]满足arr[i - 1] <= Math.min(arr[i], arr[j])使arr[i]、arr[j]配对
					if (i > 0 && dp[i - 1][j] == 1
							&& arr[i - 1] <= Math.min(arr[i], arr[j])) {
						dp[i][j] = 1;
					}
				}
			}
		}
	}
	return dp;
}