梅花桩_动态规划（Python）

关于初始化

数组 dp 中存储着对应 nums 位置的桩最大次数，所以创建的时候默认为 1，因为当前桩本身就是一步。

关于状态转移方程

其中 nums[j] < nums[i]，即扫描 i 前面的桩，如果有比 i 小的话就使用状态转移方程 dp[i] = max(dp[i], dp[j] + 1)，方程的意思是————如果前面某个桩（桩j）比 桩i 小，那么从那个桩踩上 桩i 的话自然就多了一步，我们拿这个踩完之后的步数 dp[j] + 1 跟当前存储的最大步数 dp[i] 比较一下，选个大的放进去。

while True:
    try:
        n, nums = int(input()), list(map(int, input().split()))
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        print(max(dp))
    except:
        break