I am coding brute force approach for one coding problem - I need to count the maximum score path in the array with maximum step k.

Input: nums = [1,-1,-2,4,-7,3], k = 2 Output: 7 Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

And I encountered a problem with calculating complexity. My thought was that on each elemnt we may call function k times, so time and space are O(k^n), where n is length of the array. My second guess: for first element we call function at most 1 time, for second 2 times (that is if k > i) and so on. So we have sum 1 2 ... k k ... k = ((1 k) / 2)k ((k k) / 2) / (n-k) = O(k^2). I think the first one is correct, but I can't tell for sure why :/

Here's my Java code:

public int maxResult(int[] nums, int k) {
    return maxResult(nums, k, nums.length - 1);
}

private int maxResult(int[] nums, int k, int index) {
    if (index == 0)
        return nums[0];
    int max = Integer.MIN_VALUE;
    int start = index - k < 0 ? 0 : index - k;
    
    for ( int i = start; i < index; i   ) {
        int res = maxResult(nums, k, i);
        System.out.println(i);
        max = Math.max(res, max);
    }
    return max   nums[index];
}

CodePudding user response：

The recurrence relation for your code for a particular k is

C(n) = sum(C(n-i) for i = 1...k) for n>k
C(n) = C(1)   C(2)   ...   C(n-1) for n <= k
C(1) = 1

These are the recurrence relations for the higher-order Fibonacci numbers, shifted by k-1 places. That is, C(n) = kFib(k, n k-1). The k-Fibonacci numbers grow as Theta(alpha^n) where alpha is some constant based on k -- for k=2, alpha is the golden ratio, and as k increases, alpha gets closer and closer to 2. (Specifically, alpha is is the positive root of (x^k - x^(k-1) - ... - x - 1)).

Therefore C(n) = kFib(k, n k-1) = Theta(alpha^(n k)).

Because alpha is always less that 2, O(2^(n k)) is a simple correct bound, although not a tight one.