algorithm - 我怎样才能为此制定准确的复发率？

Question

N buildings are built in a row, numbered 1 to N from left to right. Spiderman is on buildings number 1, and want to reach building number N. He can jump from building number i to building number j iff i < j and j-i is a power of 2 (1,2,4, so on). Such a move costs him energy |Height[j]-Height[i]|, where Height[i] is the height of the ith building. Find the minimum energy using which he can reach building N?

Input:

First line contains N, number of buildings. Next line contains N space-separated integers, denoting the array Height.

Output:

Print a single integer, the answer to the above problem.

所以，我想到了这样的事情:

int calc(int arr[], int beg, int end, )
{
    //int ans = INT_MIN;
    if (beg == end)
        return 0;
    else if (beg > end)
        return 0;
    else
    {
        for (int i = beg+1; i <= end; i++ ) // Iterate over all possible combinations
        {
            int foo = arr[i] - arr[beg]; // Check if power of two or not
            int k = log2(foo);
            int z = pow(2,k);
            if (z == foo) // Calculate the minimum value over multiple values
            {
                int temp = calc(arr,i,end);
                if (temp < ans)
                    temp = ans;
            }
        }
    }
}

以上是我试图解决的问题，这里是链接:https://www.codechef.com/TCFS15P/problems/SPIDY2 然而，上述重现并不完全正确。我是否也必须在此传递 answer 的值？

Answer 1

我们可以从任何 (n-2^0),(n-2^1),(n-2^2)... 建筑物到达第 n 栋建筑物。因此，我们需要从 1 开始处理建筑物。对于每个建筑物 i，我们计算从任何较早的建筑物 j 到达那里的成本，其中 i-j是2的幂并取最小的成本。

int calc(int arr[],int dp[],int n) {
    // n is the target building
    for(int i=1; i<=n; i++) dp[i]=LLONG_MAX;  //initialize to infinity
    dp[1]=0;  // no cost for starting building
    for(int i=2; i<=n; i++) {
        for(int j=1; i-j>=1; j*=2) {   
            dp[i]=min(dp[i], dp[i-j]+abs(arr[i]-arr[i-j]));
        }
    }
    return dp[n];
}

时间复杂度为 O(n*log(n))。