題目

小明和朋友玩跳格子游戲，有n個連續格子組成的圓圈，每個格子有不同的分數，小朋友可以選擇從任意格子起跳，但是不能跳連續的格子，不能回頭跳，也不能超過一圈:給定一個代表每個格子得分的非負整數數組，計算能夠得到的最高分數。
輸入描述
給定一個數例，第一個格子和最后一個格子收尾相連，如: 2 3 2
輸出描述
輸出能夠得到的最高分，如: 3
說明
1 <= nums.length <= 100
0 <= nums[] <= 1000
示例1:
輸入
2 3 2
輸出
說明只能跳3這個格子，因為第一個格子和第三個格子收尾相連
示例2
輸入
1 2 3 1
輸出
4
說明
1+3=4

思路

先不考慮首尾限制，原題轉化為，在一個數組中，找到非連續的格子組合，使其得分最大。
可以考慮動態規劃解決。以數據為例：94 40 49 65 10
定義dp[i]代表，在前i個數據時，滿足條件的最高分數
初始值：
dp[0]代表只有一個數據，得分應該為nums[0]
dp[1]代表在前兩個數據跳，不能相鄰，所以dp[1]=max(nums[0],nums[1])
對于i>1的情況，dp[i]分兩種情況，取當前值和不取當前值；
如果取當前值，那么最大值為：dp[i-2]+nums[i]
如果不取當前值，那么最大值為：dp[i-1]
dp[i]應該為兩者的較大值，即dp[i]=max(dp[i-2]+nums[i]，dp[i-1])
從上面的結果來看，我們只關心當前值的上一個值和上上個值，可以使用兩個變量來代替dp。
現在考慮首尾限制，可以分為一下兩種情況：

1. 選了第一個就不能選擇最后一個
2. 不選第一個則可以選擇最后一個

分別按照不考慮的邏輯計算上面兩種情況的結果，然后取較大結果即可。

題解

package hwod;import java.util.Arrays;
import java.util.Scanner;public class JumpCell {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();System.out.println(jumpCell(nums));}private static int jumpCell(int[] nums) {int length = nums.length;if(length==1) return nums[0];if(length==2) return Math.max(nums[0], nums[1]);return Math.max(jumpCellRange(nums, 0, length - 2), jumpCellRange(nums, 1, length - 1));}private static int jumpCellRange(int[] nums, int start, int end) {int before = nums[start], after = Math.max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {int temp = after;after = Math.max(before + nums[i], after);before = temp;}return after;}
}

推薦

如果你對本系列的其他題目感興趣，可以參考華為OD機試真題及題解（JAVA），查看當前專欄更新的所有題目。