一个坏蛋要去盗窃一排房子,每个房子都藏有一笔钱(函数参数nums记录了每个房子的钱的数量),盗窃的限制条件是,如果某两个相邻的房子同时被盗了,会触发安保系统,也就是说不能连续地盗窃房子. 求:这个坏蛋最多能盗取多少钱?
看得出题目是要求一个最优解,即安排这个窃贼的行动路线,让他拿到最多的钱.路线有很多种,目标是求最优解,似乎是动态规划题目?那么就试试分析状态转移方程:
f(n) : 代表窃贼在前n个房子最多能拿到多少钱,n==nums.size()时,即是我们要的解