好失败呀

发表于 更新于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

我本不是属于那种悲观的人，但在某天某个时辰某一秒会觉得自己真的好失败啊，当然大多是时候还是积极乐观的。失败可以被铭记，但绝不能陷入那样的情绪中去，他会摧毁一个人。写这篇文章就是发现自己的不足做下的总结并努力改变的一次记录。来吧，勇敢地面对它！

事件

前几天上一节算法设计与分析实验课，老师让做两道“简单”的算法题，我饶有兴趣地准备施展身手，没想到啊没想到，开始半小时就放弃了，因为实在是不知道怎么做啊，始终没有一个我觉得较为完美的解决方案，虽然有一些想法了，但实施加完善还是有很多错误的。这下我的自信心彻底崩塌了，就这，我还想毕业直接出去找工作，有人要吗？难不成去工地搬砖去？好失败啊！

我是属于那种好胜心比较强的，将近2个小时一道题也没有头目，挺打击人的，之后4、5个小时对这俩题都充满反感，没有回过去看一眼，很多人是不是也会这样啊！但是还是要面对的，这才是我自己啊！

开始解决

那些杀不死你的，会让你变得更强大！

下面是第一题在LeetCode搜到的

72. 编辑距离

题目地址

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例1： >输入：word1 = "horse", word2 = "ros"
>输出：3
>解释：
>horse -> rorse (将 'h' 替换为 'r')
>rorse -> rose (删除 'r')
>rose -> ros (删除 'e')

示例2： >输入：word1 = "intention", word2 = "execution"
>输出：5
>解释：
>intention -> inention (删除 't')
>inention -> enention (将 'i' 替换为 'e')
>enention -> exention (将 'n' 替换为 'x')
>exention -> exection (将 'n' 替换为 'c')
>exection -> execution (插入 'u')

题目描述大概就是这样，虽然示例和实验时的不一样，但题干是一模一样，这在LeetCode也算一道经典的题了！

begin

不看题解不知道，这是一道动态规划的问题，啊？动态规划，早有耳闻它的大名，真遇到了，果然名不虚传啊。看题解有些费力，一些地方看不懂，所以我就先从动态规划下手了。

我在B站看了这个动态规划视频，真心觉得讲的非常好，学到了不少东西，尤其对动态规划这种思想深深敬佩，太厉害了。

视频里讲了三个例题，将动态规划呈现在初学者的面前。

下面是我的简要总结，有机会我会把三个例题详细说一说。

动态规划

A 计数问题 B 最值问题 C 可行性问题

一、确定状态

  1. 最后一步
  2. 子问题

二、转移方程

三、初始条件和边界问题

初始条件：用转移方程算不出来，需要手工定义
边界情况：数组不能越界

四、计算顺序

做动态规划就按上面的来

针对这个题

一、初始条件

  1. 最后一步： dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数

所以，

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；

当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：

141-1

第一行，是 word1 为空变成 word2 最少步数，就是插入操作

第一列，是 word2 为空，需要的最少步数，就是删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}

题解参考

作者：powcai
链接：https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/

详细题解

总结

如果想再试试其他类的动态规划问题可以尝试零钱兑换、不同路径、跳跃游戏、青蛙过河，要说的是这些题可能用动态规划解不是最优方案，但都是能做的。

说句题外话，前些日发生了一件事，“大连理工研究生自杀”，一个文章的标题是这样写的——大连理工研究生自杀，遗言曝光：这世界一直教我们成功，却没教会我们接受平庸。看到这样的遗言挺有感悟的，是啊，从生到是这个世界，周围的所有人、家长、老师、朋友，都在Push我们希望我们能成功，但成功的永远是少部分，成功这种向上的心态精神是好的，但对一些人会有很大的压力，包括我，反而没有人教会我们去接受平庸，平庸也不是什么坏事，平庸也可以不平凡啊！

追求成功的路上要放平心态，勇敢的面对失败，没什么大不了的。