-3

Suppose we have an π‘š*𝑛 grid, let 𝑖=0,...,π‘šβˆ’1 and 𝑗=0,...,π‘›βˆ’1. For each grid point we have an array 𝑆𝑖𝑗 of size 𝑁 that serves as local score function. We want to to find a way that assigns every grid point a number π‘Žπ‘–π‘— in 0,...,π‘βˆ’1, which maximize the scoring function that is the sum of local scoring functions, minus the absolute value of difference of neighboring π‘Žπ‘–π‘— :

Scoring function

So the question is, can we efficiently solve the problem by dynamic programming? Moreover is the problem NP-complete?

Improve this question
0
Load 6 more related questions Show fewer related questions

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.