基于递归 + 打表

由于题目不能循环，第一思想肯定是换递归，但其实还有迭代器（本身还是循环，所以还是依题意使用递归

基本思想

由于python最大递归层数默认1000左右层，**即使修改最大,计算机好像也只能接近5000层**
而本题数据**50000**，不能常规递归
借用打表将数据分段（我是以4000为一个单位
找到在哪个区块，再递归

Python3 代码

class Solution(object):
    import sys
    sys.setrecursionlimit(100000000)  # 修改递归层数上限
    line = [1,8002000,32004000,72006000,128008000,200010000,288012000,392014000,\
            512016000,648018000,800020000,968022000,1152024000,1352026000]  # 表
    i = 0
    s = 0  # 记录答案
    m = 1  # 记录起点
    def getSum(self, n):
        self._get(n)
        if self.m > 4000:
            self.m -= 1  # 修正起点
        res = n-self.m
        self.s += self.line[self.i]
        self.dig(res)
        return self.s

    def _get(self,n):  # 确定区块
        if n <= 0:
            self.i -= 1
            self.m -= 4000
            return 0
        self.m += 4000
        self._get(n-4000)
        self.i += 1
        return 0

    def dig(self,n):  # 递归
        if n == 0:
            return 0
        self.m += 1
        self.s += self.m
        self.dig(n-1)
        return 0