Lesson 15: NumberSolitaire (Number Solitaire)

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

似たような問題は既にやっていますね。Lesson 11:FibFrogです。
実際、自分としては、なぜLesson 15でやることになっているdynamic programmingがここにでて来ているのか、不思議におもっていました。
http://codility-lessons.blogspot.tw/2015/03/lesson-11-fibfrog-fib-frog.html


とにかく、やるべきことは殆どFibFrogの問題と殆どおなじですね。

今回は配列max_val[]を用意し、とりあえずINT_MINでクリアしましょう。これは問題で可能な範囲の一番小さい数字よりも小さいものです。ただmax_val[0]だけはスタート地点になりますので、A[0]を代入しておきます。

そして、これから配列を順番に先頭からみていきます。

スタート地点から順に、現在の位置のmax_val[]と、 飛ぶ事が可能な場所のA[]の要素をたし（点数をたし）、それが、その該当位置のmax_val[]の要素より大きければ、値を更新します。

これをN-2のポジションまで繰り返せば、N-1のポジションで得られる最大の値がわかることになりますね。

これで１００％のスコアになります。

#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];
}