ARTS #135

Algorithm

本周选择的算法题是：Cherry Pickup II。

规则

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

Robot #1 is located at the top-left corner (0, 0), and
Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
When both robots stay in the same cell, only one takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Solution

Top Down:

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        @cache
        def dp(row, col1, col2) -> int:
            ans = grid[row][col1]
            if col1 != col2:
                ans += grid[row][col2]
            if row < m-1:
                ans += max(
                    [dp(row+1, new_col1, new_col2) 
                    for new_col1 in range(max(0, col1-1), min(col1+2, n))
                    for new_col2 in range(max(0, col2-1), min(col2+2, n))])
            return ans
        return dp(0, 0, n-1)

Bottom Up:

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[[0]*n for _ in range(n)] for __ in range(m)]

        for row in reversed(range(m)):
            for col1 in range(n):
                for col2 in range(n):
                    ans = grid[row][col1]
                    if col1 != col2:
                        ans += grid[row][col2]
                    if row < m-1:
                        ans += max(dp[row+1][new_col1][new_col2]
                                      for new_col1 in [col1, col1+1, col1-1]
                                      for new_col2 in [col2, col2+1, col2-1]
                                      if 0 <= new_col1 < n and 0 <= new_col2 < n)
                    dp[row][col1][col2] = ans

        return dp[0][0][n-1]

Review

The Pyramid of Coding Principles

非常好的总结，引用下文章的图：

总结下各个层级原则的侧重点：

Make it work - 无论做什么，首先要能用
YAGNI - You Aren’t Gonna Need It - 不要设计当前用不到的功能、不要保留无用代码，如果需要，你可以从 VCS 里找回
KISS - Keep It Simple Stupid - 保持简单易懂
DRY - Don’t Repeat Yourself - 不要重复，不要 WET(Write Everything Twice)
Clean Code - 为清晰的意图写清晰简明的代码，无论是创建一个方法、函数、模块还是变量名
Standing On The Shoulder of Giants - 利用工业标准和成熟的技术，而不是随意创建自己的标准
Boy Scout Rule - “总是让营地比你来时更干净”，这是很容易忽视的原则，每当我们开发新功能或维护现有功能时，我们必须始终对我们的代码库进行一些改进，它不一定是一个大的修复，我们也可以做一个小修复，例如重命名变量、删除空格、使代码具有相同的缩进等等，随手除草罢了
Make it fast - 在代码层面满足了易于维护、优化、可读性后，最后就可以聚焦如何让程序更快了，比如数据库索引、调整架构、引入缓存策略等

一个好的手艺人(craftsman)理解重构需要时间，最好能平衡所有的原则，而不是只在第一阶段做 YAGNI，这意味着要在每个迭代/里程碑中同时使用这些原则，但根据项目所在阶段分配好时间和精力，避免背负大量的技术债。

Tip

还是不够理解“管理是逆人性的”这句话，既要做逆人性的事，又需要做到顺人心，真的是非常非常难。

“小步快跑、快速迭代”几乎已经是产品研发的方法论了，软件开发之所以可以这样做，是因为原型（prototype）并不只是模型（model），不等于将来一定要另起炉灶，完全能够在原型的基础上直接做出最后的成品，这样的方式使得你可以利用在开发过程中一路产生的新想法，不断推陈出新，如同画出一个大致准确的轮廓，然后再逐步地加工出来。不过更重要的是，这样做有助于鼓舞士气。

Y Combinator 的创始人 - Paul Graham 在他的著作《黑客与画家》中提到过：

士气是设计的关键因素。令我吃惊的是，大家很少提到这一点。我的一位美术启蒙老师告诉我：如果你觉得画某样东西很乏味，那么你画出来的东西就会真的很乏味。比如，假设你必须画一幢建筑物，你决定从每一块砖头开始画起。你觉得自己可以坚持下去，但是画到一半的时候突然感到很厌倦，于是你就不再认真观察每块砖头并画出它们各自不同的特点，而是以一种机械重复的方式草草地把砖头画完了事。这样一来，你的作品效果就很差，甚至还不如一开始就不采用写实手法，只是若隐若现地暗示砖头的存在。
先做出原型，再逐步加工做出成品，这种方式有利于鼓舞士气，因为它使得你随时都可以看到工作的成效。开发软件的时候，我有一条规则：任何时候，代码都必须能够运行。如果你正在写的代码一个小时之后就可以看到运行结果，这好比让你看到不远处就是唾手可得的奖励，你因此会受到激励和鼓舞。其他艺术领域也是如此，尤其是油画。大多数画家都是先画一个草图，然后再逐步加工。如果你采用这种方式，那么从理论上说，你每天收工的时候都可以看到整体的效果，不会对最后的成品一点感觉都没有。跟你说实话吧，画家之间甚至流传着一句谚语：“画作永远没有完工的一天，你只是不再画下去而已。”这种情况对于第一线的程序员真是再熟悉不过了。

由此可以看出“小步快跑”并不只是单纯的“试错迭代”，还有一个原则是保障大方向要正确，就像过去说的“做正确的事比把事情做正确重要”，特别是对那些需要创意的工作、需要迎合市场需求快速变化的工作、落地周期较长的工作来说，更需要采用这种方法。

现在很少听到人们谈论士气这个词，但它真实存在于我们的日常活动中。

Algorithm

规则

Solution

Review

Tip

Share