@@ -0,0 +1,2436 @@
+//  Copyright 2021 The KeepTry Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage backtracing;%0A%0Apublic class Leetcode1799MaximizeScoreAfterNOperations %7B%0A  /*%0A%0A  1 %3C= n %3C= 7%0A  nums.length == 2 * n%0A  1 %3C= nums%5Bi%5D %3C= 10%5E6%0A%0A  */%0A  /*%0A  Idea:%0A  - DP(top down) + cache the result by representing the status with bit mask + recursion + backtracking%0A  - Runtime O(n%5E3) time. Eache recursion is N%5E2,N=2n, recursion depth is n. Without take cache into account.%0A  Note:%0A    %3C%3C has lower priority than +%0A  */%0A%0A  public static int maxScore(int%5B%5D nums) %7B%0A    return backtracking(1, nums, 0, new int%5B1 %3C%3C nums.length%5D);%0A  %7D%0A%0A  /*%0A  t: without it, no way to know which time current recursion is of to receive the score.%0A  status: with it to represent current status.%0A  cache: with it to keep current status's max score, avoid duplicate calculation.%0A  */%0A  private static int backtracking(int t, int%5B%5D nums, int status, int cache%5B%5D) %7B%0A    if (t == nums.length / 2 + 1) %7B // or status == (int) Math.pow(2d, nums.length * 1d) - 1%0A      return 0;%0A    %7D%0A    if (cache%5Bstatus%5D == 0) %7B%0A      int score = 0;%0A      for (int i = 0; i %3C nums.length; i++) %7B%0A        if (0 != (status & 1 %3C%3C i)) continue;%0A        for (int j = i + 1; j %3C nums.length; j++) %7B%0A          if (0 != (status & (1 %3C%3C j))) continue;%0A          score =%0A              Math.max(%0A                  score,%0A                  t * gcd(nums%5Bi%5D, nums%5Bj%5D)%0A                      + backtracking(t + 1, nums, status + (1 %3C%3C j) + (1 %3C%3C i), cache));%0A        %7D%0A      %7D%0A      cache%5Bstatus%5D = score;%0A    %7D%0A    return cache%5Bstatus%5D;%0A  %7D%0A%0A  private static int gcd(int a, int b) %7B%0A    return b == 0 ? a : gcd(b, a %25 b);%0A  %7D%0A%0A  // --------------------------------------------------------------------------%0A  public static void main(String%5B%5D args) %7B%0A    System.out.println(maxScore(new int%5B%5D %7B3, 4, 6, 8%7D) == 11);%0A    System.out.println(maxScore(new int%5B%5D %7B1, 2%7D) == 1);%0A  %7D%0A%7D%0A

Leetcode 1799. Maximize Score After N Operations