动态规划问题之打家劫舍问题

hi，everybody，my friend,今天，我们继续来学习动态规划相关问题，今天，我们要学习的是打家劫舍问题，我们接着往下看

一.题目描述

我们来仔细分析一下这个题目，如题目所描述的那样。

来看示例一,有人可能会发出这样的疑问，为什么不可以选择偷第一家和第三家呢，如果放在打家劫舍（1）中，这样做是可以的，但是在本题中，这样是不符合要求的，因为第一家和第三家是相连的，这样会触发报警系统。

接着来看示例二，在示例一对题目理解的基础上，对这个示例，我们只可以选择偷第二家和第四家（选择一），或者偷第一家和第三家（选择二）。在第一个选择中，得到的金额是3，第二个选择中，得到的金额是4，所以选择1,3家

二.讲解算法原理

本题的思想是通过分类讨论，将环形的问题，转化成打家劫舍1类型的问题

1.状态表示

根据到达第i家时，对第i家是否进行盗窃，我们需要第一两个数组

f[i-1]：表示到达第i家时，对第i家进行盗窃后，得到的最大金额。

g[i-1]:表示到达第i家时，不对第i家进行盗窃，得到的最大金额。

2.状态转移方程