幸運門票（算幸運數字量，具有所有數字的特定金額）

Question

這裏是problem

給你一個號碼1≤N≤50每票都有2N個位數。如果前N位數字的總和等於其最後N位數字的總和，我們稱它爲幸運票。你也得到了數字中所有數字的總和。你的任務是計算一定數量的幸運數字，具有所有數字的指定總和。

對於輸入2 2輸出爲4（0101，0110，1001，1010）

你能幫我解決這個問題呢？什麼是最低複雜度？

Answer 1

如果需要的總和是s，那麼每一半都必須有總和s/2。現在，您需要找到f(n, s/2)：多少個n位數字的總和爲s/2。知道f(n, s/2)，你可以在一行中得到答案（試着自己找出答案）。

至於如何計算f(n, m)：這是標準的DP。你有像f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9)遞歸公式。這裏，0, 1, 2, .. 9是給定數字的最後一位數字的所有可能選項。如果最後一位數字是k，那麼其餘的是(n-1)-長整數數字m - k。

希望它有幫助。

PS根據問題約束，您需要某種長算法來傳遞它。