1. Algorithm

62. 不同路径(中等)

描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?

示例:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
思路:

动态规划

令 dp[i][j] 是到达 i, j 最多路径。
动态方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意,对于第一行 dp[0][j],或者第一列 dp[i][0],由于都是在边界,所以只能为 1。

class Sulution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
分析:
  • 时间复杂度:O(m*n)
  • 空间复杂度:O(m*n)
优化:

使用一维数组记录变量,空间复杂度降为 O(n)。

class Sulution {
    public int uniquePaths(int m, int n) {
        int[] sum = new int[n];
        Arrays.fill(sum, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                sum[j] += sum[j - 1];
            }
        }
        return sum[n - 1];
    }
}

2. Review

What is clean code? 什么是整洁的代码?

作者从《Clean Code》这本书说起,它被认为是程序员的必读书,作者概括了三个关键概念:

  • 技术手艺很重要。代码不仅要正常工作,而且要让其他人长期受益。拙劣的代码在边缘磨损的速度比你想象的要快得多。
  • 今天的额外努力会减轻明天痛苦。一开始写出好代码并经常重构,日后就会节省的时间和金钱。
  • 你的代码不是你自己的。对作者来说,过于聪明的技巧、黑客和编程手法只是有趣的。对他人友好的代码才是可取的。

那究竟什么是 Clean Code 呢?作者给出了自己的观点:

  • 整洁代码是简洁的。不是算法或系统的复杂性,而是实现上的简约。
  • 整洁代码是可读的。代码规约有助于写出可读性好的代码。
  • 整洁代码是经过深思熟虑的。假定未来有代码使用者,一看到你的代码就懂。
  • 整洁代码是经过测试的。没人写得出完美的代码,经过测试的代码是整洁的。
  • 整洁代码是经过实践的。要一直写整洁代码,不断练习来提高技能。
  • 整洁代码是经常被重构的。尽可能多地重构,不要担心出问题。
  • 整洁代码符合 SOLID 原则。确保你的代码灵活、可维护、长久。

3. Tip

读到《深入理解计算机系统》 第二章 深入理解计算机系统之信息的表示和处理,了解了整数的表示和信息存储方法。理论知识有用么?当然有用。整形溢出是编程中经常遇到的问题,知道整数的表示方式后,会尽量规避溢出的错误。比如二分法中的取中数,mid = (low + high) / 2 就潜在溢出的风险,而 mid = low + (high - low) /2则不会,这样的程序更健壮。

4. Share

都说 deadline 是第一生产力,但是也不要总拖到最后,这时往往会因为做得太快而导致质量下降。日常有规划地进行,一步一个脚印,这样才能走得更远。