2017阿里内推笔试题–算法工程师(运筹优化)
题目
沐哲是一个菜鸟仓库的一个拣货员，但他有非常个怪异的习惯。每次拣货的重量都要比之前拣的一个轻，每次拣到货后都可以得到1块钱，沐哲想知道这样最多能赚多少钱
32 34 7 33 21 2
13 12 3 11 26 36
16 30 22 1 24 14
20 23 25 5 19 29
27 15 9 17 31 4
6 18 8 10 35 28
沐哲可以从仓库的某个货架开始拣货，下一步可以往上走，也可以往下走，当然，向左向右也可以，但必须使得下一个货物重量减小，才会去拣。在上面的仓库中，一条可拣货的路径为 25-22-3。当然30-23-20-16-13-12-3可以拣的货更多。这也是赚钱最多的一条路径。

要求
输入行数、列数和数据矩阵，输出所赚的最大钱数。
例子:
输入:
6 6
32 34 7 33 21 2
13 12 3 11 26 36
16 30 22 1 24 14
20 23 25 5 19 29
27 15 9 17 31 4
6 18 8 10 35 28
输出:
7


分析
用一个强化学习的思路来解
设置一个dp矩阵，记录每个点的当前最大收益
遍历矩阵，对于每个点A
如果周围有仓库重量比A大的点s，且s的dp值大于等于A
用s更新a。dp(a)=dp(s)+1
复杂度是 点的数量*最长路径 

row,col = 6,6

data = [[32,  34,   7,  33,  21,   2],
            [13,  12,   3,  11,  26,  36],
            [16,  30,  22,  1,   24,  14],
            [20,  23,  25,  5,   19,  29],
            [27,  15,   9,  17,  31,   4],
            [ 6,  18,   8,  10,  35,  28]]

def isInside(row,col,i,j):
    return (i in range(row)) and (j in range(col))

dp=[[0 for j in range(col)] for i in range(row)]

def arround(i,j):
    if isInside(row,col,i+1,j):
        if data[i+1][j]>data[i][j] and dp[i+1][j]>=dp[i][j]:
            return True
    if isInside(row,col,i-1,j):
        if data[i-1][j]>data[i][j] and dp[i-1][j]>=dp[i][j]:
            return True
    if isInside(row,col,i,j+1):
        if data[i][j+1]>data[i][j] and dp[i][j+1]>=dp[i][j]:
            return True
    if isInside(row,col,i,j-1):
        if data[i][j-1]>data[i][j] and dp[i][j-1]>=dp[i][j]:
            return True
    return False

def max_around(i,j):
    t=dp[i][j]
    if isInside(row,col,i+1,j):
        if data[i+1][j]>data[i][j] and dp[i+1][j]>=dp[i][j]:
            t=dp[i+1][j]
    if isInside(row,col,i-1,j):
        if data[i-1][j]>data[i][j] and dp[i-1][j]>=dp[i][j]:
            t=dp[i-1][j]
    if isInside(row,col,i,j+1):
        if data[i][j+1]>data[i][j] and dp[i][j+1]>=dp[i][j]:
            t=dp[i][j+1] 
    if isInside(row,col,i,j-1):
        if data[i][j-1]>data[i][j] and dp[i][j-1]>=dp[i][j]:
            t=dp[i][j-1]
    return t+1

while(1):
    t=0
    for i in range(row):
        for j in range(col):
            if arround(i,j):
                dp[i][j]=max_around(i,j)
                t=1
    if t==0:
        break
print(max(max(dp))+1)