We've been on 3 cruises; the first was our honeymoon and was booked months in advance; the other two were last minute. We were booked on a Royal Caribbean months in advance and 2 weeks before the trip they changed the itinerary, so we canceled (they refunded our deposit) and switched to Holland America and it was the best cruise so far! Last year we booked a HAL cruise 3 weeks out and it was a lot of fun, even though I had a bad cold. We booked directly with HAL in both cases and it was inexpensive, IMO. I think the last one was about $300/person (7 days). Cruisecritic.com is a great source of information and if you sign up with them they'll e-mail you last minute deals. As a PP said, your biggest problem may be airfare. We're within driving distance to 4 ports, so fortunately, that's never been an issue for us.