Minimum Cost

Problem Statement

Minimum Cost Problem Description The integers 1, 2, 3, ..., n mark n stepping stones on a line. Stepping on stone i costs cost[i - 1] , where cost is a 0-indexed array of length n . You start off the line at coordinate 0 , which is not a stone and is free. A single move carries you forward by any whole number of coordinates from 1 up to k . You pay the cost of each stone you land on, and the walk is finished only when you land exactly on stone n -- there is no credit for jumping clear over it. Report the minimum total cost of a finished walk. Input Format Line 1: the integer n , the number of stones. Line 2: n space-separated integers, the array cost . Line 3: the integer k , the largest move allowed. Output Format A single integer: the minimum total cost of landing on stone n . Examples Example 1 Input: 5 4 3 9 3 1 2 Output: 7 The walk 0 -> 2 -> 4 -> 5 pays 3 + 3 + 1 = 7 , and nothing cheaper exists. Example 2 Input: 4 1 2 3 4 2 Output: 6 The walk 0 -> 2 -> 4 pays 2 + 4