京东烽火台编程交流
/** *做题的时候看题目看乱了,结束后才在牛客网友提示下明白了题目意思,明白意思后第一感觉是动态规划,于是用动态规划试着实现了一下 *思路:利用一个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; }
#京东#