The second game, melee, definitely had a more traditional engine running it, too many ~bugs~ fantastic features to have been taking advantage of lookup tables.
I actually wonder if a version of Smash Bros could have worked on NES with lookup tables for physics? The existing games are 3d but the physics are all 2d.