软家on campus面试

9月26号,进行的on campus面试,一个和善的小哥哥。没有behavior question!!!

上来就直接问简历,简历问了10分钟,出了一道面经题。9个小球,外表大小一致,其中一个质量很轻。有一个天平,问至少需要几次能称出结果。
两次分三堆,分三堆,一直下去。

Coding是假如给的是n个球,写一个程序。需要clarify不考虑lucky case。
两种方法,递归或者dp。一直分三堆,取三堆中次数大的那一个。被问到两种方法的优劣。

一个星期后收到onsite邀请

请问这题dp怎么做呢?