Shape optimization is a challenging task in many engineering fields, since the numerical solutions of parametric system may be computationally expensive. This work presents a novel optimization procedure based on reduced order modeling, applied to a naval hull design problem. The advantage introduced by this method is that the solution for a specific parameter can be expressed as the combination of few numerical solutions computed at properly chosen parametric points. The reduced model is built using the proper orthogonal decomposition with interpolation (PODI) method. We use the free form deformation (FFD) for an automated perturbation of the shape, and the finite volume method to simulate the multiphase incompressible flow around the deformed hulls. Further computational reduction is done by the dynamic mode decomposition (DMD) technique: from few high dimensional snapshots, the system evolution is reconstructed and the final state of the simulation is faithfully approximated. Finally the global optimization algorithm iterates over the reduced space: the approximated drag and lift coefficients are projected to the hull surface, hence the resistance is evaluated for the new hulls until the convergence to the optimal shape is achieved. We will present the results obtained applying the described procedure to a typical Fincantieri cruise ship.