type
status
date
slug
summary
tags
category
icon
password
😉
Hi there, 上一部分简单描述了个人对动规概念上的一些了解，但动态规划这类问题在实际求解的时候往往因为比较抽象而难以寻找到思路，这部分希望通过分享一些心得及题解做一个记录和探讨。

求解思路

确定是否可以用动规解决

首先可以明确的是，动态规划方法的提出就是为了用“空间换时间”，避免重复计算问题带来过高的时间复杂度。因此，若问题存在重复计算的子问题，且整体最优能由局部最优推导，则适用动态规划。
就经验而言，动态规划问题的求解思路可分为两步：确定状态转移方程和确定边界条件。

一、确定状态转移方程

状态转移方程是动态规划的核心，需明确以下两点：

定义状态

  • 用 dp[i]、dp[i][j] 等符号表示子问题的解，例如：
    • 斐波那契数列：dp[i] 表示第 i 项的值。
    • 背包问题：dp[i][j] 表示前 i 个物品在容量 j 时的最大价值。
  1. 找到状态转移关系
      • 分析子问题如何依赖更小的子问题，用公式表达递推关系。例如：
        • 斐波那契数列：dp[i] = dp[i-1] + dp[i-2]
        • 最长递增子序列：若 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)
        • 路径问题：dp[i][j] = dp[i-1][j] + dp[i][j-1]（向右或向下走）

二、确定边界条件

边界条件是递推的起点，需明确初始状态，避免越界或错误转移：
  1. 简单问题的边界
      • 斐波那契数列：dp[0] = 0, dp[1] = 1
      • 爬楼梯问题：dp[0] = 1（无台阶时方案数为1），dp[1] = 1
  1. 多维问题的边界
      • 网格路径问题：第一行和第一列初始化为 1（只有一条路径）。
      • 背包问题：dp[0][j] = 0（无物品时价值为0），dp[i][0] = 0（容量为0时无法装物品）。
  1. 特殊情况的处理
      • 若问题中存在障碍物（如网格中的障碍），需在边界条件中跳过障碍。
      • 某些状态可能非法（如索引为负数），需通过条件判断或初始化规避。
 

部分题解

一、打家劫舍问题（Leetcode198）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
示例 2：

思路

  • 首先思考该问题是否可以用动规解决
其实该问题可以抽象为最大非连续子集的和问题，而该类问题如果采用暴力枚举法则存在大量重复问题带来的过量计算开销。而该问题同时能够由局部子问题表示，因此是典型的动态规划问题。
  • 确定问题状态转移方程
在房间大于两间的情况中，对于第n个房间，有以下两种情况：
  1. 第n间房可偷，那么第n-1间房则不可偷，则当前收益可表示为dp[n-2] + nums[n]。
  1. 第n检方不可偷，那么就投了第n-1间房，表示为dp[n-1]
则该问题转移方程可写作：
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
最后返回dp[n-1]即可（注：n为提供的数组长度）
  • 确定问题边界
首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
故边界条件写作：
dp[0] = nums [0]
dp[1] = max(nums[0], nums[1])

题解

二、删除并获得点数（Leetcode740）

给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
示例 2：

思路

这个题其实本质上是一个打家劫舍问题，可以将其拆分理解：
把原数组转换成一个新数组，新数组的下标i所对应的值为原数组的元素i在原数组中数字的总和，比如原数组[2, 2, 3, 3, 3, 4],转换为新数组就是[0, 0, 4, 9, 4]。在新数组中，下标0和1表示在原数组中没有0和1这两个数，新数组下标2的值是4，表示在原数组中，所有2的总和是4。
换的目的就是可以从新数组中得到删除nums[i]而得到的点数，也就是可以打劫的金额。因为删除nums[i]后，还要删除nums[i] + 1和nums[i] - 1，在新数组中就意味着不能取相邻的元素，不能取相邻的元素和打家劫舍也是一样的。接下来就可以使用打家劫舍的方式解答了

题解