Posts List

一周LeetCode习题精选——动态规划(2)

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

一周LeetCode习题精选——动态规划

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