Dopamine (DA) in the nucleus accumbens (NAc) is a critical signal for both learning and motivation. While DA release dynamics are often associated with reward prediction errors, they also scale remarkably well with a state-value signal – expectations of reward from an animal’s current state. However, computing value in real-world environments poses a substantial computational problem. Expectations of future rewards from a given state depend on future actions and their reward likelihood. Computing state value, therefore, necessitates assumptions about future navigational choices. Furthermore, values could be cached for quick access during behavior, or they could be computed on-the-fly to flexibly evaluate options. We investigated what strategy the brain uses to compute value in the NAc DA signal. We measured DA release dynamics in the NAc using the fluorescent biosensor dLight1.3b in Long-Evans rats (n=7) as they foraged for reward in a novel naturalistic decision-making task, the Triangle Maze. As in real-world environments, the Triangle Maze requires rats to evaluate navigational options to pursue probabilistic reward, while movable barriers periodically alter path structures. We first confirmed that spatial-state-value estimates significantly explain NAc DA dynamics during navigation. We then leveraged this relationship to test how NAc DA was estimating value. Prior to a navigational choice point, NAc DA scaled with expectations about the subsequently taken navigational trajectory, reflecting realistic assumptions about future behavior. Finally, we found evidence suggesting that NAc DA is computed on-the-fly when navigational decisions require planning. NAc DA was released to a greater degree during flexible versus stereotyped periods of behavior, especially following changes in state-transition matrix structure. Insights into how the brain computes value will help inform our current models of decision making, including the assumptions we build into artificial agents.