In this paper we consider optimal control of constrained, discontinuous, discrete-time, piecewise affine systems with state and input dependent disturbances. We seek to precompute, via dynamic programming, an explicit control law for these systems when a piecewise affine cost function is utilized. The main difficulty with this problem class is that, even for initial states for which the value function of the optimal control problem is finite, there might not exist a control law that attains the infimum. Hence, we propose a method that is guaranteed to obtain a sub-optimal solution, and where the degree of sub-optimality can be specified a priori. This is achieved by approximating the underlying sub-problems with a piecewise parametric linear program.