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

永恒的蓝色梦想

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not i | j:
                    pass
                
                elif not i:
                    grid[i][j] += grid[i][j - 1]
                    
                elif not j:
                    grid[i][j] += grid[i - 1][j]
                    
                else:
                    grid[i][j] += (a if (a := grid[i - 1][j]) > (b := grid[i][j - 1]) else b)

        return grid[-1][-1]

动态规划现学现用

ouyunfu

def f349(ar:list)->int:
    def f(L,m,n):
        if m==1 and n==1:
            return L[m-1][n-1]
        if m>1 and n==1:
            return f(L,m-1,n)+L[m-1][n-1]
        if m==1 and n>1:
            return f(L,m,n-1)+L[m-1][n-1]
        if m>1 and n>1:
            return max(f(L,m-1,n),f(L,m,n-1))+L[m-1][n-1]
    x,y=len(ar),len(ar[0])
    return f(ar,x,y)

ar=[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
print(f349(ar))

Unicorn#

def solve(Map):
    n = len(Map)
    m = len(Map[0])
    Val = []
    for i in range(n):
        Val.append([])
        for j in range(m):
            Val[i].append(0)
    Val[0][0] = Map[0][0]
    for i in range(n):
        for j in range(m):
            if i > 0:
                a = Val[i-1][j] + Map[i-1][j]
            else:
                a = 0
            if j > 0:
                b = Val[i][j-1] + Map[i][j-1]
            else:
                b = 0
            if a or b:
                Val[i][j] = max(a, b)
    return Val[n-1][m-1]

archlzy

def fun349(input_list):
    m,n = len(input_list[0]),len(input_list)
    dp = [[0 for _i in range(m)] for _j in range(n)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j][i] = input_list[0][0]
            elif i == 0:
                dp[j][i] = dp[j-1][i] + input_list[j][i]
            elif j == 0:
                dp[j][i] = dp[j][i-1] + input_list[j][i]
            else:
                dp[j][i] = max(dp[j][i-1], dp[j-1][i]) + input_list[j][i]
    return dp[-1][-1]

l0stparadise

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

为啥我看都看不懂。。。。。

l0stparadise

现学了itertools。。。。

import itertools
import numpy as np
def f349(arr1):
    lenth=len(arr1)
    width=len(arr1[0])
    arr2=np.reshape(arr1,lenth*width)
    iter_move=(width-1)*str(1)+(lenth-1)*str(width)
    move_list=set(itertools.permutations(iter_move,lenth+width-2))
    # print(move_list)
    count=0
    init=arr2[0]
    sum_list=[]
    for i in move_list:
        for h in i:
            count=count+int(h)
            init += arr2[count]
        count=0
        sum_list.append(init)
        init = arr2[0]
    return max(sum_list)

派生小生

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]
    col = line = 1
    while col < m:
        while line < n:
            fuzhu[col][line]=max([fuzhu[col][line-1],fuzhu[col-1][line]])+grid[col][line]
            line += 1
        col +=1
        line = 1
    return fuzhu[m-1][n-1]

派生小生

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

借鉴了大神的思路，然后自己修改了下，思路转变为使用while求出一行行的最大值。

tzczjh

def solve(chessboard):
    # 简单dp
    # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + chessboard[i][j]
    # 每个chessboard[i][j]只被访问一次 所以可以用chessboard[i][j]存储dp[i][j]的值

    m = len(chessboard)
    if not m:
        return None
    n = len(chessboard[0])

    for i in range(m):
        for j in range(n):
            if not (i + j):
                continue 
            if not i:
                chessboard[i][j] += chessboard[i][j - 1]
            elif not j:
                chessboard[i][j] += chessboard[i - 1][j]
            else: 
                chessboard[i][j] += max(chessboard[i][j - 1], chessboard[i - 1][j])
    return chessboard[m - 1][n - 1]

永恒的蓝色梦想

l0stparadise 发表于 2020-3-11 22:15
为啥我看都看不懂。。。。。

动态规划

776667

from itertools import permutations

def fun349(grid):
    path = [0 for i in range(len(grid[0])-1)] + [1 for i in range(len(grid)-1)]
    max_value = 0
    for i in permutations(path):
        position = [0,0]
        value = grid[0][0]
        for j in i:
            if j == 0:
                position[0] += 1
            elif j == 1 :
                position[1] += 1
            value += grid[position[0]][position[1]]
        if value > max_value:
            max_value = value
    return max_value

fan1993423

永恒的蓝色梦想 发表于 2020-3-12 08:59
动态规划

动态规划有没有好的资料推荐学习

永恒的蓝色梦想

fan1993423 发表于 2020-3-12 12:16
动态规划有没有好的资料推荐学习

我也只是从网上随便找了篇……不知道小甲鱼有没有

zltzlt

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

96 ms

zltzlt

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

56 ms

zltzlt

风魔孤行者 发表于 2020-3-11 15:34
自己都有点看不下去

输入以下数据超时：

[[7, 0, 8, 8, 0, 3, 5, 8, 5, 4], [4, 1, 2, 9, 9, 6, 0, 8, 6, 9], [9, 7, 1, 1, 0, 1, 2, 4, 1, 7]]

zltzlt

mdphd 发表于 2020-3-11 15:35
这个算法在m，n很大时应该会很快

60 ms

zltzlt

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

70 ms

zltzlt

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

输入以下数据超时：

[[7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5], [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6], [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8], [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4], [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4], [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9], [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4], [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2], [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3], [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7], [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7], [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9]]

zltzlt

flamezyy 发表于 2020-3-11 16:33
估计超时了

嗯，输入以下数据超时：

[[7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5], [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6], [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8], [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4], [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4], [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9], [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4], [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2], [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3], [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7], [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7], [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9]]