假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱 。
示例 :
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 解题思路考虑所有可能的抢劫方案过于困难。一个自然而然的想法是首先从最简单的情况开始。记：
\(f(k) =\) 从前 k 个房屋中能抢劫到的最大数额，\(A_i\) = 第 i 个房屋的钱数。
首先看 n = 1 的情况，显然 f(1) = \(A_1\) 。
再看 n = 2，\(f(2) = max(A_1 , A_2 )\)。
对于 n = 3，有两个选项:
抢第三个房子，将数额与第一个房子相加。
不抢第三个房子，保持现有最大数额。
显然，你想选择数额更大的选项。于是，可以总结出公式：
\(f(k) = max(f(k – 2) + A_k , f(k – 1))\)
我们选择 \(f(–1) = f(0) = 0\) 为初始情况，这将极大地简化代码。
答案为 \(f(n)\)。可以用一个数组来存储并计算结果。不过由于每一步你只需要前两个最大值，两个变量就足够用了。
时间复杂度：\(O(n)\)。其中 n 为房子的数量。
空间复杂度：\(O(1)\)。
给出两个单词word1和word2，计算出将 word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符、删除一个字符、替换一个字符。
示例 :
输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') 解题思路我们的目的是让问题简单化，比如说两个单词 horse 和 ros 计算他们之间的编辑距离 D，容易发现，如果把单词变短会让这个问题变得简单，很自然的想到用 D[n][m] 表示输入单词长度为 n 和 m 的编辑距离。
具体来说，D[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。
当我们获得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。
每次只可以往单个或者两个字符串中插入一个字符
那么递推公式很显然了
如果两个子串的最后一个字母相同，word1[i] = word2[i] 的情况下：
\(D[i][j] = 1 + \min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1] - 1)\)
\(D[i][j]=1+min(D[i−1][j],D[i][j−1],D[i−1][j−1]−1)\)
否则，word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：
\(D[i][j] = 1 + \min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])\)
\(D[i][j]=1+min(D[i−1][j],D[i][j−1],D[i−1][j−1])\)
所以每一步结果都将基于上一步的计算结果，示意如下：
同时，对于边界情况，一个空串和一个非空串的编辑距离为 D[i][0] = i 和 D[0][j] = j。
综上我们得到了算法的全部流程。
