Esse teste em especifico serve para verificar como você lida com recursividade e o quanto você consegue fazer um código eficiente, pois em uma implementação normal desse algoritmo ele teria uma complexidade de O(2^n), que seria o que a maioria dos devs implementaria, porém, você pode utilizar o conceito de DynamicProgramming para implementar esse algoritmo, e por consequência, a complexidade dele diminuiria para O(n). Esse é um conceito bem importante pois demonstra que você é capaz de quebrar um problema grande em problemas menores e resolvê-lo com eficiência.

Uma boa ideia é treinar no HackerRank, por exemplo, pois lá tem vários desafios que podem ser resolvidos dessa forma, e normalmente as grandes empresas de TI usam o mesmo tipo de algoritmo que tem lá no HackerRank (as vezes o próprio hackerrank, inclusive) para avaliar os candidatos.

P.S.: Uma vez eu reprovei num teste da Amazon justamente por causa disso :(