For Bushido, LS has always worked best for me to take it all the way to 120. I used the Yamotsu Warriors in the Yamotsu Mines because the 3rd room has 2 that spawn in there. The Warriors have a lot of HP's, so by the time you've got one dead, the 2nd has respawned already, which has you swinging non stop with no waits for the respawn.
For warriors, the only skill I can think of that you can raise without fighting monsters is Chivalry.