DP 经典问题 1 - LIS

lis.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

from itertools import combinations
def naive_lis(seq):
    '''最长上升子（非下降）序列 Longest Increasing Subsequence，基本解法
    首先生成一个序列可能的所有子序列，比如说给定数组[1, 2, 3]，那么所有可能的子序列是
    [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]。
    然后从中挑选满足所有上升的子序列。最后算出其中拥有最大长度的一个。
    '''
    subs = []
    for length in xrange(len(seq), 0, -1):    # 生成从0开始到len(seq)的所有可能的长度
        for sub in combinations(seq, length): # 生成所有可能的子序列
            if list(sub) == sorted(sub):      # 如果子序列为升序，那么满足条件
                print sub
                subs.append(sub)
    return max(map(len, subs))                # 在所有的结果中，取长度最大的一个

def rec_lis(seq):
    '''LIS memoization解法。
    用recursion的方法来解题，最关键的一点是学会假设。举个例子，在解fib问题的时候我们假设
    fib(n-1) 和 fib(n-2)是有解的，所以公式 fib(n) = fib(n-1) + fib(n-2)成立。如果
    此时fib(n-1)没有解的话，那么fib(n)是不可求的。先不要急着说『怎么可能没有解呢』，用数学
    的方式来思考，所谓假设，只是数学证明的一个步骤而已。

    同理，用recursion的方法来解DP问题，我们也要假设，假设dp[i-1]的最优解存在，也就是当处理
    dp[i]的时候，我们先假设dp[i-1]是已知的，在此基础上怎么求出dp[i]呢？如果你开始能够这么
    思考dp问题的话，那么其实答案就已经有了。对于从0开始到i结束的最优解dp[i]，如果position i的
    元素大于position i-1的元素，那么dp[i] = dp[i-1] + 1，否则，dp[i]就要重新计算（不连续）。
    '''
    def dp(cur):
        res = 1
        for pre in xrange(cur):
            if seq[pre] <= seq[cur]:
                res = max(res, 1 + dp(pre))
        return res
    return max(dp(i) for i in xrange(len(seq)))

def iter_lis(seq):
    '''LIS iteration解法
    上面的recursion解法效率并不高，所以最后写出来的dp都是iterative，但是用recursion
    可以很好的帮助我们理解怎么样假设前一个解存在，然后推导出一个动态转移方程来。能够推导出来
    这个方程，剩下的就是根据转移方程中涉及的下标来添加for循环了。
    '''
    dp = [1] * len(seq)                               # 初始化成满足要求的最小值
    for cur, val in enumerate(seq):                   # 在recursion版本的基础上加一个for循环
        for prev in xrange(cur):                      # 从这里开始就是上一个版本实现过的代码逻辑了
            if seq[prev] <= seq[cur]:                 # 判断i-1和i是否满足条件
                dp[cur] = max(dp[cur], dp[prev] + 1)  # 更新动态转移方程
    return max(dp)

if __name__ == '__main__':
    s1 = [1, 2, 3]
    print "naive solution of LIS. Complexity O(N^3) result is \n", naive_lis(s1)

    print 'Momoization solution of LIS, result is \n', rec_lis(s1)

    print 'Iteration solution of LIS. Complexity O(N^2) result is \n', iter_lis(s1)

Hard to understand your second solution: