LCR 089. 打家劫舍

2023-08-18
北京
本文字数：1645 字
阅读完需：约 5 分钟

前言

今天突然看到了这道动态规划的题目，感觉动态规划的思想还是非常实用的。

百度百科中的介绍，总结经验，求解内容依赖当前状态，又受上一步决策的影响。这类问题可往动态规划的方向想一想

概念

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20 世纪 50 年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

基本结构

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理（最优子结构性质）

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性 [8] 。

子问题的重叠性

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间

题目

LCR 089. 打家劫舍

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：nums = [1,2,3,1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：nums = [2,7,9,3,1]

输出：12

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。

偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析

这是一道典型的动态规划问题，不过题目有点不符合社会主义价值观，😄

拆解问题：

dp[i][0]: 第 i 号房屋不偷窃的最大收益

dp[i][1]: 第 i 号房屋偷窃的最大收益

如果要求利益最大化：i > 1 时

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

dp[i][1] = dp[i - 1][0] + nums[i]

初始值：

dp[0][0] = 0;

dp[0][1] = nums[0];

public int rob(int[] nums) {
    // dp[i][0]: 第 i 号房屋不偷窃的最大收益    // dp[i][1]: 第 i 号房屋偷窃的最大收益    // 利益要求最大化，i > 1 时    // dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])    // dp[i][1] = dp[i - 1][0] + nums[i]
    int len = nums.length;    int[][] dp = new int[len][2];
    dp[0][0] = 0;    dp[0][1] = nums[0];
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);        dp[i][1] = dp[i - 1][0] + nums[i];    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);}