Lesson 15: NumberSolitaire (Number Solitaire)

Lesson 15: NumberSolitaire
https://codility.com/programmers/lessons/16

We already have solved a similar problem, Lesson 11:FibFrog.
Indeed, I was wondering why we have to use the dynamic programming concept  for this problem as it is scheduled in Lesson 15
http://codility-lessons.blogspot.tw/2015/03/lesson-11-fibfrog-fib-frog.html

Anyway, what we do is the almost the same as in the FibFrog problem. 
We prepare the array max_val[] and then initialize it with INT_MIN, which is smaller than the possible minimum value in the given conditions, except max_val[0], which is set the initial point we get when we start at A[0].

We begin from the position 0 and take the value at max_val[0]. Then, we add this point with the points we can obtain at each cell we can reach by the next jump and update the maximum value if it is larger than one that we obtained so far at the cell.

We repeat this until the cell we can perform the last jump (at the position N - 2, right before the goal).


This strategy gives the 100% score as below.

#include <alloca.h>
#include <limits.h>

int solution(int A[], int N) 
{
    int  memsize = sizeof(int) * N;
    int* max_val = (int*)alloca(memsize);
    
    //initialize the each cell with INT_MIN except the first one.
    max_val[0] = A[0];
    for (int i = 1; i < N; i++){
        max_val[i] = INT_MIN;
    }    
    
    //do dynamic programming for jump
    for (int pos = 0; pos < N - 1; pos++){
        
        //throw the dice (1-6)
        for (int j = 1; j <= 6; j++){
            //if out of range, neglect.
            int jump_pos = pos + j;
            
            //not to jump out of the range.
            if (jump_pos >= N){
                continue;
            }
            
            //update each cell's max value.
            int tmp = A[pos + j] + max_val[pos];
            max_val[jump_pos] = max_val[jump_pos] < tmp ? tmp : max_val[jump_pos];
        }
    }
    
    return max_val[N - 1];
}