Yes, but as this blog post shows, you can apply dynamic programming (and then various other optimizations) to make it fast for common uses.