ORID41

这次周赛第三题我本来是想用BFS来做的，但是发现自己实现不了，所以还需要加强自己的练习。

1514. Path with Maximum Probability 解题报告

用什么算法？

BFS，因为你需要找出最优路径
我当时一开始是想用BFS来做的，但是后来发现你要走每一个点，然后找出到end这个点最优路径（概率最大的），所以我觉得DFS好像才能满足条件。所以我就是这写这个DFS，但是最后还是没能实现。
我觉得最主要原因还是你BFS用得不够熟练吧，这道题还要回过头来复习一下。

198. House Robber 解题报告

用什么算法

dp
因为这道题可以用之前计算过的结果来找到最高值。
dp的四大步骤

1. 确定状态
   找到n-1之前的结果（就是最后你要求的值是怎么从之前计算结果得出来的）
   这道题就是说如果你rob 最后一个房子，那么之前一栋你就不可以，所以你的答案就要从之前一栋房子的价值nums[i - 1] 和当前房子价值加上i - 2之前rob过的所有房子的值加起来。
2. 转化方程
3. 初始化
   这里因为是序列化动归，所以dp[0] = 0 就代表第一个永远是空，之后才开始计入动归里面。这样保证了你可以在第n（也就是nums.length）的时候得到答案，而不用考虑初始化dp[0]是否有问题。
   dp[1] = nums[0] 因为这里只有一种可能 （题目要求是不能连续偷相邻的房子）

写出来code 就是

public int rob(int[] nums) {
  int[] dp = new int[nums.length + 1]; //因为你多了一个0， 所以用nums.length + 1
  //init 
  dp[0] = 0;
  dp[1] = nums[0];
  for (int i = 2; i <= nums.length; i++) {
      dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]) //nums[i-1] 代表你要偷当前的房子，所以你要加上之前不相邻房子算过的和，也就是dp[i - 2] （因为i -1）是相邻的房子，不能偷。
  //如果你不偷当前的房子，你就要把前一栋房子的值和偷当前房子的值进行比较，选最高的那个。因为你要获取最大利益。
  }

  return dp[nums.length];
}

213. House Robber II 解题报告

用什么算法

这道题就是上一题的进阶版，就是把一排房子变成了一圈房子，所以首尾两栋房子就不能一起偷了，一开始我还想要看我到底偷没偷第一栋（其实那样也可以解决，就是麻烦一点）
看了9c的视频发现其实你完全可以把这道题拆解成偷了第一栋，那么dp[1] = nums[0] 然后不算最后一栋房子
和没偷第一栋，也就是dp2[1] = nums[1] 然后算最后一个房子，我直接新开了一个数组记录第二种情况，这两个数组可以在一个for loop 里面就完成计算，最后比一下他俩最小值就可以了。代码：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0 || nums == null) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[n];
        int[] dp2 = new int[n];
        //init for rob first house 
        dp[0] = 0;
        dp[1] = nums[0];
        //init for not rob first house
        dp2[0] = 0;
        dp2[1] = nums[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
            dp2[i] = Math.max(nums[i] + dp2[i - 2], dp2[i - 1]);
        }
        int result = Math.max(dp[n-1], dp2[n-1]);
        return result;
    }
}