动态规划

LeetCode 55 链接：Jump Game 本题可以使用动态规划解决。动态规划主要有四个步骤： 使用递归回溯方法 使用备忘录方法优化（自顶向下的动态规划） 消除递归方法（自底向上的动态规划） 使用其他方法优化时间/空间复杂度 ...

LeetCode 198 链接：House Robber 本题使用动态规划解决。首先需要分析题目的递归关系：当强盗到达第i间房屋时，他可以选择抢，也可以选择不抢。如果抢劫这间房屋，根据题目要求，他必定没有抢劫第i-1间房屋，但他可能抢劫第i-2间房屋。如果不抢劫第i间房屋，那么他可能抢劫第i-1间房屋。这两个选择造成抢劫得来金钱的不同。设rob(i)为前i间房屋抢劫得来金钱的最大值，第一种需要计算前i-2间房屋抢劫金钱的最大值加上第i间房屋抢劫的金钱。第二种只需要计算前i-1间房屋抢劫金钱的最大值。两者需取其中最大值，由此得出递归关系： ...