1415.md

1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Solution 1 (time O(2^n), space O(n^2))

# DFS
class Solution(object):
    def getHappyString(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        self.ans = ""
        self.cnt = 0

        def dfs(cur_str):
            if self.cnt == k:
                return
            if len(cur_str) == n:
                self.cnt = self.cnt + 1
                if self.cnt == k:
                    self.ans = cur_str
                return
            for new_c in ["a", "b", "c"]:
                if len(cur_str) != 0 and new_c == cur_str[-1]:
                    continue
                dfs(cur_str + new_c)
        
        dfs("")
        return self.ans