[已解决]Python：每日一题 349

zltzlt

今天的题目：

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。

可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。

给定一个棋盘 grid 包含每个礼物的价值，计算最多能拿到多少价值的礼物。

示例 1:

输入：
[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
输出：12
解释：路径 1→3→5→2→1 可以拿到最多价值的礼物

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

tzczjh

2020-3-12 07:36:05

def solve(chessboard):

    # 简单dp

    # dp[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j] = max(dp[i - 1][zxsq-anti-bbcode-j], dp[zxsq-anti-bbcode-i][j - 1]) + chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j]

    # 每个chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j]只被访问一次 所以可以用chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j]存储dp[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j]的值



    m = len(chessboard)

    if not m:

        return None

    n = len(chessboard[zxsq-anti-bbcode-0])



    for i in range(m):

        for j in range(n):

            if not (i + j):

                continue 

            if not i:

                chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j] += chessboard[zxsq-anti-bbcode-i][j - 1]

            elif not j:

                chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j] += chessboard[i - 1][zxsq-anti-bbcode-j]

            else: 

                chessboard[zxsq-anti-bbcode-i][zxsq-anti-bbcode-j] += max(chessboard[zxsq-anti-bbcode-i][j - 1], chessboard[i - 1][zxsq-anti-bbcode-j])

    return chessboard[m - 1][n - 1]

跳转到最佳答案楼层

TJBEST

高亮而且有奇怪的字符

zltzlt

TJBEST 发表于 2020-3-11 13:31
高亮而且有奇怪的字符

这么快？乱码已调整

mdphd

感觉除了遍历没什么特别高效的算法

mdphd

找到一个好算法！

vidyhe

可是没有说每个单元格是多少价格呢

TJBEST

此法比较费空间，但是时间上还是不慢的。

def fun349(grid):
    m = len(grid)
    n = len(grid[0])
    fuzhu = []
    for index in range(0,m):
        fuzhu.append([0 for i in range(0,n)])
    
    minNum = min([m,n])
    fuzhu[0][0]=grid[0][0]
    for index in range(1,n):
        fuzhu[0][index]=fuzhu[0][index-1]+grid[0][index]
    for index in range(1,m):
        fuzhu[index][0]=fuzhu[index-1][0]+grid[index][0]
    for index in range(1,minNum):
        for inner in range(index,n):
            fuzhu[index][inner]=max([fuzhu[index][inner-1],fuzhu[index-1][inner]])+grid[index][inner]
        for inner in range(index+1,m):
            fuzhu[inner][index]=max([fuzhu[inner][index-1],fuzhu[inner-1][index]])+grid[inner][index]
    return fuzhu[m-1][n-1]

kinkon

TJBEST 发表于 2020-3-11 14:29
此法比较费空间，但是时间上还是不慢的。

人才啊

Geoffreylee

def f_349(lst: list) -> int:
    # 创建与原数组相同大小的0数组，记录到lst[i][j]所得到的最大值
    max_value_lst = [[0] * len(i) for i in lst]

    for i in range(len(lst)):
        for j in range(len(lst[0])):
            if i == 0 and j == 0:
                # 记录初始值
                max_value_lst[i][j] = lst[i][j]
            else:
                max_value_lst[i][j] = max(max_value_lst[i-1][j], max_value_lst[i][j-1]) + lst[i][j]

    return max_value_lst[-1][-1]


print(f_349([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))

风魔孤行者

def f(m,n):
    if m == 0:
        list1=[]
        string = 'b'*n
        list1.append(string) 
        return list1
    else:       
        list3 = []
        for each in f(m-1,n):
            for number in range(len(each)+1):
                list3.append(each[:number]+'a'+each[number:])
        return list3

def d(l):
    list1 = list({}.fromkeys(f((len(l[0])-1),(len(l)-1))).keys())
    count = []
    for each in list1:
        a = 0
        b = 0
        n = l[a][b]
        for value in each:
            if value == 'a':
                b += 1
                n += l[a][b]
            else:
                a += 1
                n += l[a][b]
        count.append(n)
    count.sort()
    return count.pop()
        
print(d([[1,3,1],[1,5,1],[4,2,1]]))          
    

自己都有点看不下去

mdphd

a = [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]
b = [[0]*(max(len(a),len(a[0])))]*(min(len(a),len(a[0])))
if len(a) <= len(a[0]):
    b = a
else:
    def transformMatrix(m):
        r = [[] for i in m[0]]
         
        for ele in m:
            for i in range(len(ele)):
                r[i].append(ele[i])
        return r
    b = transformMatrix(a)
m, n = len(b), len(b[0])
c = b[:][:]
for x in range(1, m):
    for i in range(1, x):
        b[i][x-i] = max(b[i - 1][x - i], b[i][x - i - 1]) + c[i][x - i]
    b[x][0] = b[x - 1][0] +c[x][0]
    b[0][x] = b[0][x - 1] + c[0][x]
for x in range(m, n):
    for i in range(1, m):
        b[i][x-i] = max(b[i - 1][x - i], b[i][x - i - 1]) + c[i][x - i]
    b[0][x] = b[0][x - 1] + c[0][x]

for x in range(n, m + n -1):
    for i in range(x - n + 1, m):
        b[i][x-i] = max(b[i - 1][x - i], b[i][x - i -1]) + c[i][x - i]
print(b[m - 1][n - 1])

这个算法在m，n很大时应该会很快

蒋博文

def fun349(s):
    if not s:
        return 0
    a = len(s)
    b = len(s[0])
    maxs = [0] * b
    for i in range(0, a):
        for j in range(0, b):
            ma = 0
            mb = 0
            if i > 0:
                mb = maxs[j]
            if j > 0:
                ma = maxs[j - 1]
                
            maxs[j] = max(ma, mb) + s[i][j]
    return maxs[b-1]

kinkon

不好意思上传...

def f349(lst):
    A, B = len(lst), len(lst[0])
    t = 1
    while t < B:
        lst[0][t] = lst[0][t-1] + lst[0][t]
        t += 1
    t = 1
    while t < A:
        lst[t][0] = lst[t - 1][0] + lst[t][0]
        t += 1
    for i in range(1, A):
        for j in range(1, B):
            lst[i][j] = max(lst[i][j] + lst[i][j - 1], lst[i][j] + lst[i - 1][j])
    return lst[-1][-1]

fan1993423

kinkon 发表于 2020-3-11 15:57
不好意思上传...

思路可以啊， 有什么不好意思上传的

风魔孤行者

TJBEST 发表于 2020-3-11 14:29
此法比较费空间，但是时间上还是不慢的。

大佬，看了你的代码之后写的

def f(list1,m,n):
    if m>1 and n>1:
        return max(f(list1,m-1,n),f(list1,m,n-1))+list1[m-1][n-1]
    if m==1 and n>1:
        return f(list1,m,n-1)+list1[m-1][n-1]
    if m>1 and n==1:
        return f(list1,m-1,n)+list1[m-1][n-1]
    if m==1 and n==1:
        return list1[m-1][n-1]
    
def d(list1):
    return f(list1,len(list1),len(list1[0]))

flamezyy

import itertools
def f349(grid):
    last_m = len(grid)
    last_n = len(grid[0])
    product = last_m + last_n - 2
    hor_num = last_n - 1
    hor_combinations = []
    result = []
    for i in itertools.combinations(range(1,product+1),hor_num):
        hor_combinations.append(i)
    for p in hor_combinations:
        i = 0
        j = 0
        sum = grid[0][0]  
        for q in range(1,product+1):
            if q in p:
                j += 1
                sum += grid[i][j]
            else:
                i += 1
                sum += grid[i][j]        
        result.append(sum)
    return max(result)

估计超时了

塔利班

def f349(x):
    back={(0,0):x[0][0]}
    I,J=len(x)-1,len(x[0])-1
    def dp(i,j):
        if (i,j) in back:
            return back[(i,j)]
        else:
            a=b=0
            if i>0:
                a=dp(i-1,j)+x[i][j]
            if j>0:
                b=dp(i,j-1)+x[i][j]
            back[(i,j)]=max(a,b)
            return back[(i,j)]
    return dp(I,J)

TJBEST

风魔孤行者 发表于 2020-3-11 16:23
大佬，看了你的代码之后写的

我这个思路随便用，有可能有更好的。互相交流吧

TJBEST

我个人认为对于函数传入的参数如果是列表等可更改的对象（不可hash的）还是在函数内生成一个备份。我看了大家都是 在传入的列表上面直接更改同时计算 这样原始列表数据也改了，这不符合编程规范。相当于用原始数据计算 同时有更改原始数据。我感觉不太好。

永恒的蓝色梦想

vidyhe 发表于 2020-3-11 14:27
可是没有说每个单元格是多少价格呢

这个格的值就是他的价格