动态规划Dynamic Programming学习笔记

要了解DP，需要知道递归的知识和基本的暴力搜索。

定义：

• 本质：递归
• 原问题（N）->子问题（N-1）->原问题（N）

最优子结构

• 子问题最优决策可导出原问题最优决策
• 无后效性

重叠子问题

• 去冗余
• 空间换时间（注意分析时空复杂度）

基本步骤：
四个步骤

• 构建高效的穷举方案以识别多余的处理步骤
• 设计并存储状态的方式包括使用一维数组、二维数组、三维数组以及Map结构
• 使用动态规划模型来表示状态转移方程
• 通过自底向上的方法计算最优解的策略通常采用编程实现

从实例出发，记录下思路，题目

简述一下题意：

一行房屋每家都有资金若选择被选中的房屋不能与相邻的一家冲突则问题转化为在未被选中相邻房屋的情况下如何才能获取最大的资金

设想nums数组用于记录每户人家的存款信息，在来到第n户人家时我面临两种决策选项：是否进行抢劫

若决定实施抢劫行为

若选择放弃此次抢劫机会

代码：

    public class Solution {
    
        //抢劫的第index家，Nums保存每家的