Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous day. The prisoner knows the calories of each dish for the full week, and wishes to maximize his calorie intake for the week.
I modeled the problem into a bidirected cyclic graph: l[n], h[n] are the two known arrays of costs and k the number of steps taken through the graph. (The cost to the H node at the kth step is h[k]). L represents eating the low nutrient dish, while H the high one. If you want to get to H you must pass from - first and amass no cost. The costs represent the nutrients gained when moving to each node. (They could be rewards on the nodes instead). S is the start node. The goal is to maximize the cost, given the number of maximum steps n.
I'm looking for a general direction. Does it belong to a known family of problems? If yes, how do you solve them efficiently? Dynamic programming, knapsack or some known modification of a graph traversal algorithm? Is considering it a graph problem wrong, or not particulartly helpful? Sorry for the barrage of questions.