# Single-Pointer DP Problems

Dynamic programming(DP) problems that typically use one pointer. E.g., `Integer[] memo`

.

# House Robber

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums`

representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police*.

**Example 1:**

1 | Input: nums = [1,2,3,1] |

**Example 2:**

1 | Input: nums = [2,7,9,3,1] |

## Solution

状态空间为`Integer[] memo = new Integer[nums.length]`

.

DP有两个方向, 一种是从前向后DP(`memo[i] = dp(i+1)`

), 这类问题一般可以表述为和下面类似的形式:

1 | 从第i天开始能获得的收益 = 第i天当天的收益 + 从第i+1天开始能获得的收益 |

另一种是从后向前DP(`memo[i] = dp(i-1)`

), 这类问题一般可以表述为和下面类似的形式:

1 | 截至第i天能获得的收益 = 第i天当天的收益 + 截至第i-1天能获得的收益 |

这道题的解法属于前者.

用`memo[i]`

表示从第i间房子开始能抢到的最大值. 当我在第`i`

间房子时, 我有两种选择: 抢, 不抢. 而`memo[i]`

也就等于: 当天的收益(如果抢的话) + ( `memo[i+1]`

or `memo[i+2]`

, 取决于第`i`

天抢没抢).

1 | memo[i] = Math.max( |

## Code

1 | public int rob(int[] nums) { |