论坛 › Python交流 › Python：每日一题 349

zltzlt 发表于 2020-3-11 13:30:56

Python：每日一题 349

本帖最后由 zltzlt 于 2020-3-11 13:34 编辑

今天的题目：

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

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

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

示例 1:

输入：
[
,
,

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

{:10_298:}欢迎大家一起答题！{:10_298:}

TJBEST 发表于 2020-3-11 13:31:15

高亮{:5_109:}而且有奇怪的字符

zltzlt 发表于 2020-3-11 13:32:07

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

这么快？{:10_268:}乱码已调整

mdphd 发表于 2020-3-11 13:44:57

感觉除了遍历没什么特别高效的算法{:10_243:}

mdphd 发表于 2020-3-11 13:55:37

找到一个好算法！

vidyhe 发表于 2020-3-11 14:27:48

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

TJBEST 发表于 2020-3-11 14:29:38

本帖最后由 TJBEST 于 2020-3-11 14:35 编辑

此法比较费空间，但是时间上还是不慢的。
def fun349(grid):
    m = len(grid)
    n = len(grid)
    fuzhu = []
    for index in range(0,m):
      fuzhu.append()
   
    minNum = min()
    fuzhu=grid
    for index in range(1,n):
      fuzhu=fuzhu+grid
    for index in range(1,m):
      fuzhu=fuzhu+grid
    for index in range(1,minNum):
      for inner in range(index,n):
            fuzhu=max(,fuzhu])+grid
      for inner in range(index+1,m):
            fuzhu=max(,fuzhu])+grid
    return fuzhu

kinkon 发表于 2020-3-11 15:10:05

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

人才啊{:5_106:}

Geoffreylee 发表于 2020-3-11 15:24:02

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

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

    return max_value_lst[-1][-1]


print(f_349([, , ]))

风魔孤行者 发表于 2020-3-11 15:34:30

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)
      return list3

def d(l):
    list1 = list({}.fromkeys(f((len(l)-1),(len(l)-1))).keys())
    count = []
    for each in list1:
      a = 0
      b = 0
      n = l
      for value in each:
            if value == 'a':
                b += 1
                n += l
            else:
                a += 1
                n += l
      count.append(n)
    count.sort()
    return count.pop()
      
print(d([,,]))         
    自己都有点看不下去{:10_266:}

mdphd 发表于 2020-3-11 15:35:16

本帖最后由 mdphd 于 2020-3-11 16:32 编辑

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

for x in range(n, m + n -1):
    for i in range(x - n + 1, m):
      b = max(b, b) + c
print(b)
这个算法在m，n很大时应该会很快

蒋博文 发表于 2020-3-11 15:38:01

本帖最后由 蒋博文 于 2020-3-11 15:45 编辑

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

kinkon 发表于 2020-3-11 15:57:06

不好意思上传...
def f349(lst):
    A, B = len(lst), len(lst)
    t = 1
    while t < B:
      lst = lst + lst
      t += 1
    t = 1
    while t < A:
      lst = lst + lst
      t += 1
    for i in range(1, A):
      for j in range(1, B):
            lst = max(lst + lst, lst + lst)
    return lst[-1][-1]

fan1993423 发表于 2020-3-11 16:18:54

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

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

风魔孤行者 发表于 2020-3-11 16:23:47

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
    if m==1 and n>1:
      return f(list1,m,n-1)+list1
    if m>1 and n==1:
      return f(list1,m-1,n)+list1
    if m==1 and n==1:
      return list1
   
def d(list1):
    return f(list1,len(list1),len(list1))

flamezyy 发表于 2020-3-11 16:33:24

本帖最后由 flamezyy 于 2020-3-11 17:07 编辑

import itertools
def f349(grid):
    last_m = len(grid)
    last_n = len(grid)
    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
      for q in range(1,product+1):
            if q in p:
                j += 1
                sum += grid
            else:
                i += 1
                sum += grid      
      result.append(sum)
    return max(result)

估计超时了

塔利班 发表于 2020-3-11 16:47:20

def f349(x):
    back={(0,0):x}
    I,J=len(x)-1,len(x)-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
            if j>0:
                b=dp(i,j-1)+x
            back[(i,j)]=max(a,b)
            return back[(i,j)]
    return dp(I,J)

TJBEST 发表于 2020-3-11 16:47:52

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

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

TJBEST 发表于 2020-3-11 16:53:51

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

永恒的蓝色梦想 发表于 2020-3-11 18:01:16

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

这个格的值就是他的价格

查看完整版本: Python：每日一题 349