Does a Greedy solution for ZCO SUPW Problem exist ?

general
, , ,
1

Problem : CodeChef: Practical coding for everyone

2

It’s pure Dynamic classic problem! Greedy solution would not be able to cover all path! You have to use either Dynamic programming or use Priority queue for implementation! See my Solution

3

No a greedy solution does not exist. This problem is dynamic programming.
My answer is as follows

https://www.codechef.com/viewsolution/15890333

4 
n = int(input())
c = [int(x) for x in input().split()]
if len(c) <= 3:
    print(min(c))
else:
    cost = [c[0],c[1],c[2]]
    for i in range(3,len(c)):
        cost.append(c[i] + min(cost[i-3:i]))
    print(min(cost[len(c)-3:]))

Here this pass all test cases there is a problem in test case, there the give value of n but the element they have given in next line, they are greater or lesser then value of n

5

this was my code btw xD

2 Likes
6

This is still Dynamic Programming.