题目描述

给出n行m列的矩阵，每次要取出每一行行头或者行位去掉，得到的价值为这个数加上2的第几次取次方。
问最大的价值是多少

解题思路

很容易发现每一行都是同一个处理办法去处理，行与行之间不会相互影响，那么在一行中，可以用上动态规划，要么取队头加上后面的len-1个数，要么取队尾加上len-1个数，这个求解过程中还可以用上记忆化搜索。
数据很大，也只是60分，选择简单的Python搞定高精度）Java不会。。

def dfs(l, r):

    len = r - l + 1
    k = m - len + 1 #第几次选数
    if f[l][r]: return f[l][r]
    if l == r:  return a[l] * (1 << k)
    f[l][r] = max(dfs(l + 1,r) + a[l] * (1 << k),dfs(l,r - 1) + a[r] * (1 << k))
    return f[l][r]


n,m = map(int, input().split())
ans = 0

for i in range(n):
    f = [[0] * m for j in range(m)] #m*m的0矩阵
    a = list(map(int,input().split()))
    ans += dfs(0,m - 1)
print(ans)