798. Smallest Rotation with Highest Score

Description

image-20210908191353540

Solution

Let’s first check how many times we need take to move ith element to nums[i] position where is the first index that gets point.

Take nums = [2,3,1,4, 0] as example:

1
2
3
4
5
A[0] = 2 move to 2's index, k = 3 = (0 - A[0] + 5) % 5 
A[1] = 3 move to 3's index, k = 3 = (1 - A[1] + 5) % 5
A[2] = 1 move to 1's index, k = 1 = (2 - A[2] + 5) % 5
A[3] = 4 move to 4's index, k = 4 = (3 - A[3] + 5) % 5
A[4] = 0 move to 0's index, k = 4 = (4 - A[4] + 5) % 5

For one element, after move k times, it have reached to the point that one more step move will make it lose point. So we define a array to store the index that all element firstly lose point.

And we could find that when K = k, A[i] is happened to lost point, then k = k+1, A[i] still can’t get point, but the first element on the head of the array rotate back to the tail will get new point.

So we have the recurrence relation:

1
dp[k+1] += dp[k] - 1  (Note we are counting the numer of losing point's element)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int res = 0;
        for(int i = 0; i < n; i++){
            dp[(i - nums[i] + 1 + n) % n] += 1;
        }
        for(int i = 1; i < n; i++){
            dp[i] += dp[i-1] - 1;
            res = dp[res] > dp[i] ? i : res;
        }
        return res;
    }
};