At individual points in space and time, the classical Hopf-Lax formula gives the value of the solution of a spatially homogeneous Hamilton-Jacobi equation in terms of an optimization problem. However, the Hamilton-Jacobi equations that commonly arise from nontrivial problems in Optimal Control Theory are spatially inhomogeneous. Accordingly, we present a discrete, generalized Hopf-Lax formula for solving spatially inhomogeneous Hamilton-Jacobi equations. We then suggest a primal-dual hybrid gradient method for resolving the requisite optimization problem. Because these methods are characteristic based and do not rely on discretizing spatial domains, they scale well to high dimensions. We demonstrate the efficacy of our methods on several examples in high-dimensional optimal path planning, including problems involving collaborative multi-agent control.