One more idea would be to check www.nachtzugreise.de - this is the homepage of the night-train-services of Deutsche Bahn (German Railroads). If you have a chance to do so, you could save the money you normally spent for a night in a hotel and use the Nighttrain instead of. If you dont mind to sleep in a couchette, their cheapest fares begin with 29 Euro per trip.