wq

house robber
# Please enter the commit message for your changes. Lines starting
# with '#' will be ignored, and an empty message aborts the commit.
#
# On branch master
# Your branch is up to date with 'origin/master'.
#
# Changes to be committed:
#	new file:   198.house-robber/README.md
#	new file:   198.house-robber/main.js
#
# ------------------------ >8 ------------------------
# Do not modify or remove the line above.
# Everything below it will be ignored.
diff --git a/198.house-robber/README.md b/198.house-robber/README.md
new file mode 100644
index 0000000..a2feac2
--- /dev/null
+++ b/198.house-robber/README.md
@@ -0,0 +1,27 @@
+### 题材
+
+你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
+给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
+
+### 思路
+
+动态规划则把问题分解成相互依赖的子问题
+
+    // 对于 [2, 0, 0, 4, 5]，能打劫到的最大钱财是7
+    expect(rob([2, 0, 0, 4, 5])).toBe(7);
+
+- 如果数组的长度是 1，返回第一项
+- 如果数组的长度是 2，返回第一项和第二项的最大值
+- 如果数组的长度是 3，返回 `数组长度是2（就是前两项）的值` 和 `第一项 + 最后一项的值` 的最大值
+- 如果数组的长度是 4，返回 `前三项的值` 和 `前两项得到的值 + 最后一项的值` 的最大值
+- 如果数组的长度是 5，返回 `前四项的值` 和 `前三项得到的值 + 最后一项的值` 的最大值
+  ...
+- 如果数组的长度为 n，返回 `前（n-1）项的值` 和 `前（n-2）的值 + 最后一项的值` 的最大值
+----
+    f(0) = array[0]
+    f(1) = Math.max(array[0], array[1])
+    f(n) = Math.max(f(n-1), array[-1]+f(n-2))
+
+### 问题
+
+动态规划
diff --git a/198.house-robber/main.js b/198.house-robber/main.js
new file mode 100644
index 0000000..46fd4eb
--- /dev/null
+++ b/198.house-robber/main.js
@@ -0,0 +1,57 @@
+/*
+ * @lc app=leetcode.cn id=198 lang=javascript
+ *
+ * [198] 打家劫舍
+ *
+ * https://leetcode-cn.com/problems/house-robber/description/
+ *
+ * algorithms
+ * Easy (40.42%)
+ * Likes:    391
+ * Dislikes: 0
+ * Total Accepted:    33.8K
+ * Total Submissions: 82.2K
+ * Testcase Example:  '[1,2,3,1]'
+ *
+ * 
+ * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
+ * 
+ * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
+ * 
+ * 示例 1:
+ * 
+ * 输入: [1,2,3,1]
+ * 输出: 4
+ * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
+ * 偷窃到的最高金额 = 1 + 3 = 4 。
+ * 
+ * 示例 2:
+ * 
+ * 输入: [2,7,9,3,1]
+ * 输出: 12
+ * 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
+ * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
+ * 
+ * 
+ */
+/**
+ * @param {number[]} nums
+ * @return {number}
+ */
+var rob = function (nums) {
+  var pre = 0
+  var now = 0
+  for (var i = 0; i < nums.length; i++) {
+    var temp = pre
+    pre = now
+    now = Math.max(temp + nums[i], now)
+  }
+
+  return now
+};
+
+// var rob = function (nums) {
+//   return nums.reduce((p, n) => {
+//     return [p[1], Math.max(p[0] + n, p[1])];
+//   }, [0, 0])[1];
+// }
\ No newline at end of file