This paper studies the problem of linearizing the input-output map of an analytic discrete-time nonlinear system locally around a given trajectory. Necessary and sufficient conditions are given for the existence of a regular dynamic state feedback control law under which the input-dependent part of the response of a nonlinear system becomes linear in the input and independent of the initial state. The proposed conditions are less restrictive than those obtained by Lee and Marcus for linearizing the input-output map via a static-state feedback. Instrumental in the problem solution is the inversion (structure) algorithm for a discrete-time nonlinear system. Firstly, the solvability conditions are expressed in terms of the inversion algorithm. Secondly, the proof of the existence and construction of the dynamic state feedback compensator relies on this algorithm.