针对斐波那契数列，原本的题意是从所求参数依次往base case（F(0),F(1)）去求。换个思路就是，从base case 向所求参数去凑。比如F(4)，用自顶向下的思路就是因为要求F(4)，所以我需要先求F(3)和F(2)(这样满足公式嘛)，而自底向上的思路就是要求F(4)，我可以先求F(2)(因为F(0)和F(1)已知，很轻易可以求出F(2))，这样往我们需要求的参数一步一步向上去凑，直到求到**F(4)**。

那么这种思路的伪代码就如下：

fun fib(n:Int): Int {
  	if (n < 2) return n
  	
  	var fn = 1
  	var fn1 = 0
  	var res = fn + fn1
  	for (i in 2..n) {
      	res = fn + fn1
      	fn1 = fn
      	fn = res
       }
  
  	return res
}

每一步向上求，只和前两个值有关，所以这里一共需要三个变量就可以解决。

打家劫舍的问题

一般针对有求解最值的题目，可以考虑使用动态规划来处理，在打家劫舍这一系列的题目中，我们需要求的都是能打劫到的最多的钱。

1.明确状态：可以理解为，状态是为选择提供的一种基础，对于抢劫来说，基础就是有人被你抢，所以这个题目中，一间间房屋就是我们需要的状态。（像凑硬币的题目，一种硬币其实就是一种状态）

2.明确选择：状态分析出来后，针对状态我们存在的选择只有两个，抢劫或者不抢。

3.dp方程式：dp的值要计算的当前的房间进行操作后，能得到的钱是多少，比如在第一间房，如果选择抢，那么得到的钱应该是当前房间的钱加上下下间房屋里抢的钱（中间需要间隔一个），而如果选择不抢，那么直接计算下个房间就可以了。

dp = max(dp1, currentRoomMoney + dp2)
// 这里做数据更新
dp2 = dp1
dp1 = dp

4.baseCase:其实可以从两个角度想，一个是当你下个房间能抢到的数目为0时，其实就已经结束了（因为题目给的数是非零正整数），而另一个就是房间的数目是有限的，遍历完就是结束了。

这个的时间复杂度的计算，就是子问题的个数*解决一个子问题的时间，对于抢劫一间房，执行的时间是O(1)，而子问题的个数是N，所以总的来说是O(N)的时间复杂度。

同样有自顶向下和自底向上 两种思路来实现。一般画了二叉树，使用自顶向下的方案会比较容易理解，因为这个方案是从暴力解中优化来了，解决了重叠子问题的问题。伪代码的逻辑如下，

// 自顶向下的伪代码
// 使用备忘录来优化重叠子问题
val memo = mutableMapOf<Int, Int>()
fun rob(nums: IntArray,  start:Int) {
  ...
  if (memo.containsKey(start)) return memo[start]
  val res =  max(rob(next), nums[current] + rob(next+1))
  memo[start] = res
  return res
}

// 自底向上的伪代码
fun rob (nums:IntArray) {
  for ( i in nums.lastIndex downTo 0) {
  	dp = max (dp1, nums[i] + dp2)
       dp2 = dp1
       dp1 = dp
  }
  
  return dp
}

第二个题将数组变成了环形了，环形的问题就是首尾的房间不能同时被抢，所以分别计算抢首部和抢尾部两种方法的钱，就知道了

// 将上面的循环遍历的区间从整个数组修改为指定的即可
fun rob (nums: IntArray) {
  return max(robRange(nums,  0 ,  nums.lastIndex - 1)
            , robRange(nums, 1 ,nums.lastIndex)
   )
}

第三个问题将数组变成了二叉树，在树结构上相邻的两个房间不能别抢，就是父节点如果抢了的话，就不能去抢子节点了，而是应该去抢子节点的子节点,注意：这两的子节点的子节点应该是四个了，分别是左子树的两个子节点和右子树的两个子节点。如果没有抢，那么就直接就计算子节点。

fun rob(node:Node?) {
  // 当前房间要抢，那最终的钱就是当前房间的加上子节点的子节点的钱
  rob = node.monkey + (rob(node.left?.left) ?: 0 + rob(node.left?.right ?: 0)) + (rob(node.right?.left ?: 0) + rob(node.right?.right ?: 0))
  notRob = rob(node.left) + rob(node.right)
  
  return max(rob, notRob)
}

当然，上面的方案仍然要使用备忘录来进行优化，记录已经计算过的节点。

最后是另有一个比较不错的解法

int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数 */
int[] dp(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 抢，下家就不能抢了
    int rob = root.val + left[0] + right[0];
    // 不抢，下家可抢可不抢，取决于收益大小
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

    return new int[]{not_rob, rob};
}

这个解法的思路类似于股票买卖问题，在决定一个房间是不是需要抢的选择时，可以决定下一个房间（股票问题是当前的利润来自前面一天的决定）。对于房间来说，如果当前抢了，那么下间房间一定不能抢，而如果没有抢，那么下间房间可能抢也可能不抢（股票的问题是，第i天时，手上没有持有股票，可能来自两种操作的结果，一个是前一天卖掉了，二个是前一天也没有买，所以今天也就延续了前一天的状态）。

鸡蛋掉落问题

题目的简单描述，就是说给你K个鸡蛋，然后有N层楼，问最少需要多少次能测出鸡蛋在几楼掉落刚好不碎（或者说可以测出鸡蛋的质量）。

这是一道很经典的动态规划的问题，解法还是和之前一样，有自顶向下和自底向上两种思路可以来解决这个问题。

自顶向下

在这个题目中，状态有两个，一个是鸡蛋的个数，另一个是楼层。所以对应状态的变化就是两种，首先是楼层的变化，我们可以想象为有一个鸡蛋，那么至少需要多少次可以去确定楼层，这里可以用二分搜索的方式来处理，就是$\log(N)$的时间复杂度；第二个就是鸡蛋个数的变化，其实就是可操作次数的Max值。

状态如何转移呢，当我们在一层楼落下鸡蛋时，只有两个可能的结果，就是蛋碎了或者蛋没有碎，蛋碎了就减少一个蛋的数目，然后继续向上搜索楼层，没碎则直接进行向下搜索楼层的操作。最后我们需要的至少的次数，就是遍历过程中最小的操作。那么dp的状态转移方程就是

$$dp = min \lbrace dp(k, n - mid) + 1, dp(k - 1, mid - 1) + 1; k \in K, mid = (lo + hi) / 2 \rbrace$$

这个方程的详细解释就是，当我们使用二分法进行楼层的搜索时，这层的状态结果有两个，其中$dp(k, mid - 1)$对应的是在这层路鸡蛋掉下去没有碎，鸡蛋的个数不会减少的情况下，后面总共还需要多少次来测试，所以后面加1的目的是加上这次，同时，因为鸡蛋没有碎，说明楼层的高度还不够，那么下次就应该搜索当前楼层的上面楼层区间了；后面也是一样，如果鸡蛋碎了，鸡蛋数目需要减少，同时应该搜索的区间就是当前楼层的下面楼层了。

最后的就是结束条件(base case)，什么情况下就不能测试了，需要看我们的状态：首先是楼层，当楼层N 为0的时候，肯定没有法测了，这就是不存在的条件；第二，如果鸡蛋数目K为1的时候，不就是上面我们讲的最简单的情况了，不过需要注意的是，这个考虑的是最坏的情况，不是说一个鸡蛋，用二分的方式至少$log(N)$次就可以了，而是需要$N$次，最坏的情况就是从一楼开始，到楼顶才测出来。

伪代码如下：

fun dp(K:Int, N:Int):Int {
  	if (K == 1) return n
  	if (N == 0) return 0
  	// 使用备忘录模式来优化重叠子问题
  	if (memo[K][N] != -1) return memo[K][N]
  
       var lo = 1
  	var hi = N
  	var res = Int.MAX_VALUE
  	while (lo <= hi) {
      	val mid = (lo + hi) / 2
      	// 碎了，那么接下来需要计算的是K- 1个鸡蛋在(N - mid) 楼中掉落的子问题
      	val brohen = dp(K - 1,  n - mid)
      	val notBrohen = dp(K, mid - 1)
      	
      	if (borken > notBroken) {
          	hi = mid - 1
          	res = min(res, borken + 1)
           } else {
          	lo = mid + 1
          	res = min(res, notBroken + 1)
          }
      	memo[K][N] = res
      }
  	return res
}

时间复杂度：有两个状态，每一个状态组合下的子问题解决的时间复杂度是$log(N)$，一共有$K \cdot N$个问题，所以总的时间复杂度就是$ K \cdot N \cdot log(N)$。

自底向上

自底向上就是使用dp数组来解决问题，可以换个思路来思考题目，题目说的是在N层楼的情况下，K个鸡蛋至少需要F次才知道哪层楼才能刚好摔碎$\implies$也就是说我们可以算，K个鸡蛋，操作F次的情况下，最多可以测试的最高楼层数是多少，只要这个最高楼层数大于等于题目给出的N，那么这个F就是我们的答案了。

根据这个思路可以得出dp的计算方式dp[k] = dp[k] + dp[k - 1] + 1，dp[k] 代表的在当前的楼层，是k个鸡蛋的时候，能测出的楼层数目，所有最后的+1代表的就是本次楼层，等于后面的dp[k]代表的是本次楼层落下后，鸡蛋没有碎，那么继续向上测试楼层总共能测出还有多少楼，而dp[k - 1]代表的是如果鸡蛋正好在本层楼落下碎了，想楼下测试总共还能测出多少楼。最后就是看dp[K]和N的关系，当dp[K] > N时，就符合上面说的K个鸡蛋操作了F次后，最多有**dp[K]**层楼刚刚碎。 代码如下:

fun dp(K;Int, N:Int): Int {
 	val dp = IntArray(K + 1)
   var ans = 0
   while (dp[K] < N) {
       // 这里为啥是K倒序到1 而不是从1正序遍历，还没搞懂
     	for (k in K downTo 1) dp[k] = dp[k] + dp[k - 1] + 1
     	ans++
   }
   return ans
}

这样计算的时间复杂度就更好一些，为 $O(KN)$。