Digital quantum simulation on quantum systems require algorithms that can be implemented using finite quantum resources. Recent studies have demonstrated digital quantum simulation of open quantum systems on Noisy Intermediate-Scale Quantum (NISQ) devices. In this work, we develop quantum circuits for optimal simulation of Markovian and Non-Markovian open quantum systems. The circuits use ancilla qubits to simulate the environment, and memory effects are induced by storing information about the system on extra qubits. We simulate the amplitude damping channel and dephasing channel as examples of the framework and infer (Non-)Markovianity from the (non-)monotonic behaviour of the dynamics. Further, we develop a method to optimize simulations by decomposing complex open quantum dynamics into smaller parts, that can be simulated using a small number of qubits. We show that this optimization reduces quantum space complexity from to for simulating the environment.