贪心算法和动态规划/最长递增子序列LIS等问题

#coding:utf-8
import scrapy
import xlwt, lxml
import re, json
import matplotlib.pyplot as plt
import numpy as np
import pylab
from scipy import linalg
import math

#贪心算法和动态规划
'''
基本归纳法：对于Ai+1，只需考察前一个状态Ai即可完成整个推理过程，它的特点是只要状态Ai确定，则计算Ai+1时无需考察更前序的状态A1...Ai-1，在图论中，常常称之为马尔科夫模型；
高阶归纳法：对于Ai+1，需考察前i个状态集{A1...Ai}才可完成整个推理过程，往往称之为高阶马尔科夫模型；
在计算机算法中，高阶马尔科夫模型的推理，叫做动态规划（dp）；马尔科夫模型的推理，对应贪心算法

说明：
    无论dp还是贪心法，都是根据A[0...i]计算A[i+1]的过程
        计算Ai+1不需要考虑其后的元素
        一旦计算完成Ai+1，再后面计算Ai+2...时，不会更改Ai+1的值
        即无后效性
    
    亦可以如下理解dp：计算Ai+1只需要知道A0...i的值，无需知道A0...i是通过何种途径计算得到的---只需知道它们当前的状态值本身即可。如果将A0...i的全体作为一个整体，则可以认为动态规划法是马尔科夫过程，而非高阶马尔科夫过程

'''

'''
贪心法：
    根据实际问题，选取一种度量标准。然后按照这种标准对n个输入排序，并按序一次输入一个量。
    如果输入和当前已构成在这种度量意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。
    这一处理过程一直持续到n个输入都被考虑完毕，则计入最优解结合中的输入子集构成这种量度意义下的问题的最优解
    这种能够得到某种量度意义下的最优解的分级处理方法，称为贪心方法。
'''

#最长递增子序列LIS
# 可通过将给定序列排序后与原序列求LCS求解

'''
长度为N的数组记为A={a0a1...an-1}
记A的i前缀串Ai=a0a1...ai-1;以ai结尾的最长递增子序列记做Si，其长度记为a[i]
假定已经计算得到了a[0,1,...,i-1],如何计算a[i]呢？

根据定义，Si必须以ai结尾，如果将ai缀到S0S1...Si的后面是否允许呢？
    如果ai>aj [j<i],则可以将ai缀到aj的后面，并且使得Sj的长度变长
从而，a[i]={max(len(Sj)+1),j<i and aj<=ai}
    需要遍历在i之前的所有位置j，找出满足条件aj<=ai的aj；
    计算得到a[0...n-1]后，遍历所有a[i]，找到最大值即为最大递增子序列的长度。
    时间复杂度为O(N^2)
可通过记录前驱求LIS本身
'''
def reverseString(s,f,to):#(字符串/数组，起始位置，结束位置)
    while (f<to):
        t=s[f]
        s[f]=s[to]
        s[to]=t
        f+=1
        to-=1
    # print(s)
def LIS(A):
    N=len(A)
    c=[0]*N
    pre=[-1]*N
    S=[]
    nLis,nindex=1,0
    for i in range(N):
        for j in range(i):
            if A[j]<=A[i]:
                if c[i]<c[j]+1:
                    c[i]=c[j]+1
                    pre[i]=j#记录前驱，以得到LIS
        if nLis<c[i]:
            nLis=c[i]#更新最大长度
            nindex=i#记录最后一个LIS字符的位置
    # print(nindex)
    while nindex>=0:
        S.append(A[nindex])
        nindex=pre[nindex]
    reverseString(S,0,len(S)-1)
    print(S)

# LIS([1,6,2,4,7,5])


'''矩阵乘积
根据矩阵相乘的定义来计算C=A X B,需要m*n*s次乘法
三个矩阵A，B，C的阶分别为a0*a1,a1*a2,a2*a3,从而（A*B）*C和A*（B*C）的乘法次数是a0*a1*a2+a0*a2*a3和a1*a2*a3+a0*a1*a3,二者一般情况下是不等的
    故，给定n个矩阵的乘积：A1*A2*...*An,Ai与Ai+1是可乘的，如何添加括号来改变计算次序，使得算法的计算量最小？
    
分析：
将矩阵乘积AiAi+1...Aj记为A[i:j],这里i<=j
    当i==j，则A[i:j]为A[i]本身
考察计算A[i:j]的最优计算次序。设计算次序在矩阵Ak和Ak+1之间断开，i=<k<j,则其相应的完全加括号方式为
    (AiAi+1...Ak)(Ak+1...Aj)
计算量：A[i:k]的计算量加上 A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量

    设计算A[i:j](1=<i=<j<=n)所需要的最少数乘次数为m[i][j],则原问题的最优解为m[1][n]
    记Ai的维数为Pi-1*Pi
    当i==j时，A[i:i]=A[i],即m[i][j]=0,i=1,2,...,n
    当i<j时m[i][j]=m[i][k]+m[k+1][j]+Pi-1*Pk*Pj
    
    从m[i][j]的递推关系式可以看出，在计算m[i][j]时，需要用到m[i+1][j],m[i+2][j]...m[j-1][j]
            -----0     i=j
    m[i][j]=------
            -----m[i][j]=m[i][k]+m[k+1][j]+Pi-1*Pk*Pj      i<j
    
    因此求m[i][j]的前提，不是m[0...i-1][0...j-1],而是沿着主对角线开始，依次求取到右上角元素
    
    因为m[i][j]一个元素的计算，最多需要遍历n-1次，共O(n^2)个元素，故算法的时间复杂度是O(n^3),空间复杂度是O(n^2)
    
'''
#p[0...n]存储了n+1个数，其中（p[i-1],p[i]）是矩阵i的阶；
#s[i][j]记录A[i...j]从什么位置断开；m[i][j]记录数乘最小值

def MatrixMultiply(p,n,m,s):
    for i in range(1,n+1):
        m[i][i]=0
    for r in range(2,n+1):
        for i in range(1,n-r+2):
            j=i+r-1
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]
            s[i][j]=i
            if i<j:
                for k in range(i+1,j):
                    t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
                    if t<m[i][j]:
                        m[i][j]=t
                        s[i][j]=k
    r=np.array(m)
    print(np.array(s))
    print(r)


p=[2,3,4,5]
n=len(p)-1
m=[[0]*(n+1) for i in range(n+1)]
s=[[0]*(n+1) for j in range(n+1)]

# MatrixMultiply(p,n,m,s)

'''
高维数组赋值问题

m=[[None]*5 for i in range(5)]#若想赋值给二维数组的指定索引元素，应当使用此方法

#对于n=[[None]*5]*5,二者初始化后是等价的，但是对于list * n—>n shallow copies of list concatenated, n个list的浅拷贝的连接；修改其中的任何一个元素会改变整个列表
'''

# 字符串的交替连接：
#   s1和s2是s3的子序列，且s1 U s2=s3
# s1,s2保持原有的相对顺序

# 分析
'''
若s1和s2没有字符重复：遍历s3的同时，考察是否是s1和s2的字符即可
若字符重复：可以用压栈的方式解决

此外，还能使用dp
状态转移函数
    令dp[i,j]表示s3[1...i+j]是否由s1[1...i]和s2[1...j]的字符组成：即dp[i,j]取值为True/False
    如果s1[i]==s3[i+j],且dp[i-1,j]为真，那么dp[i][j]为真
    如果s2[j]==s3[i+j],且dp[i,j-1]为真，那么dp[i][j]为真
    其它情况，dp[i][j]为假
    
'''
def isInterleave(s1,s2,s3):
    n,m,s=len(s1),len(s2),len(s3)
    if m+n!=s:
        return False
    dp=[[False]*(n+1) for l in range(m+1)]
    dp[0][0]=True
    # print(dp)
    for i in range(n+1):
        for j in range(m+1):
            if (i-1>=0 and dp[i-1][j]==True and s1[i-1]==s3[i+j-1]) or (j-1>=0 and dp[i][j-1]==True and s2[j-1]==s3[i+j-1]):
                dp[i][j]=True
    print(dp[n][m])
    print(dp)
    return dp[n][m]

isInterleave('aabcc','dbbca','aadbbcbcac')

'''
走棋盘/格子取数：给定m*n矩阵，每个位置是一个非负整数，从左上角开始，每次只能朝右和下走，走到右下角，求总和最小的路径

状态转移函数：
    走的方向决定了同一个格子一定不会经过两次。
    若当前位于（x,y）处，它的上一步来自于哪些格子呢？
        dp[0][0]=a[0][0]
        dp[x][y]=min(dp[x-1][y]+a[x][y],dp[x][y-1]+a[x][y])
        即 dp[x][y]=min(dp[x-1][y],dp[x][y-1])+a[x][y]
-----------------------------------------------

拓展：存在部分格子禁止通过，该信息放在二维数组blocked中
如果blocked[i][j]=True，则不能通过格子(i,j)。计算有多少条路径能够从左上角到右下角

状态转移方程
    dp[i][j]表示从起点到（i,j）的路径条数
    如果（i,j）被占用--》dp[i][j]=0
    如果不被占用：
    dp[i][j]=dp[i-1][j]+dp[i][j-1]
'''
# Catalan 卡塔兰数：

'''
何时可以考虑使用动态规划：
    初始规模下能够方便的得出结论
        空串、长度为0的数组、自身等
    能够得到问题规模增大导致的变化
        递推式---状态转移函数
    事实上，动态规划还有个‘无后效性’的要求
        一旦计算得到了A[0...i-1],那么，计算A[i]时只可能读取A[0...i-1],
        1.不会更改它们的值----过去发生的，只能承认，不能改变
        2.不需要事先知道A[i+1...n-1]的值----未来的事情，完全未知
    在实践中往往忽略无后效性这一要求，
        要么问题本身决定了他是成立的：格子取数
        要么通过更改计算次序，可以达到该要求：矩阵连乘问题
        
'''