算法-动态规划
动态规划是一种解决多阶段决策过程最优化问题的数学方法。通常需要保存决策路径的问题用回溯法，而只是求最优解的时候选择动态规划。
基本概念
- 定义：动态规划通过把原问题分解为相对简单的子问题，并保存子问题的解，避免重复计算，从而高效地求解复杂问题。它通常适用于具有最优子结构和子问题重叠性质的问题。
- 最优子结构：一个问题具有最优子结构意味着问题的最优解可以由子问题的最优解组合而成。例如，在求解最短路径问题中，从起点到终点的最短路径可以由从起点到中间点的最短路径和从中间点到终点的最短路径组成。
- 子问题重叠：子问题重叠是指在求解问题的过程中，会多次重复地求解相同的子问题。动态规划通过保存子问题的解，避免了重复计算这些子问题，从而提高了算法的效率。
解题步骤
- 确定问题的状态：状态是描述问题在不同阶段的特征。选择合适的状态表示是动态规划的关键。例如，在背包问题中，可以用背包的剩余容量和已选物品的集合来表示状态。
- 定义状态转移方程：状态转移方程描述了如何从一个状态转移到另一个状态。它通常是根据问题的最优子结构性质推导出来的。例如，在背包问题中，状态转移方程可以表示为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])，其中dp[i][j]表示前i个物品放入容量为j的背包中的最大价值，w[i]和v[i]分别表示第i个物品的重量和价值。
- 确定初始状态和边界条件：初始状态是问题的最简单情况，边界条件是状态转移方程在特殊情况下的取值。例如，在背包问题中，初始状态可以是dp[0][j] = 0（没有物品时，背包价值为 0），边界条件可以是dp[i][0] = 0（背包容量为 0 时，背包价值为 0）。
- 计算最优解：根据状态转移方程和初始状态、边界条件，通过递推或递归的方式计算出问题的最优解。通常可以使用自底向上（递推）或自顶向下（记忆化搜索）的方法进行计算。
应用举例
打家劫舍
链接: https://leetcode.cn/problems/Gu0c2T/
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组nums，请计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
class Solution:
def rob(self, nums: List[int]) -> int:
len_nums = len(nums)
# 定义边界条件
if len_nums == 0:
return 0
if len_nums == 1:
return nums[0]
dp = []
dp.append(nums[0])
dp.append(max(nums[1], nums[0]))
for idx in range(2, len_nums, 1):
dp[idx % 2] = max(dp[(idx - 1) % 2], dp[(idx - 2) % 2] + nums[idx]) # 只需要用两个值来缓存中间结果
return dp[(len_nums - 1) % 2]打家劫舍2
链接：https://leetcode.cn/problems/PzWKhm/
环形房屋，即第一个房屋和最后一个房屋也不能同时被打劫。该问题可以看做是求以下两个子问题的最大值：
- 房屋0 到 房屋len - 2 (不打劫最后一间房屋)
- 房屋1 到 房屋len - 1 (不打劫第一间房屋)
def helper(nums, start, end):
dp = []
dp.append(nums[start])
if start < end:
dp.append(max(nums[start], nums[start + 1]))
for i in range(start + 2, end + 1, 1):
j = i - start
dp[j % 2] = max(dp[(j - 1) % 2], dp[(j - 2) % 2] + nums[i])
return dp[(end - start) % 2]
class Solution:
def rob(self, nums: List[int]) -> int:
len_nums = len(nums)
if len_nums == 0:
return 0
if len_nums == 1:
return nums[0]
return max(helper(nums, 0, len(nums) - 2), helper(nums, 1, len(nums) - 1))粉刷房子
链接：https://leetcode.cn/problems/JEj789/description/
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。 请计算出粉刷完所有房子最少的花费成本。 示例 1： 输入: costs = [[17,2,17],[16,16,5],[14,3,19]] 输出: 10 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。 最少花费: 2 + 5 + 3 = 10。
示例 2： 输入: costs = [[7,6,2]] 输出: 2
- 状态转移方程为：
dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + cost[i][0]
dp[1][i] = min(dp[0][i - 1], dp[2][i - 1]) + cost[i][1]
dp[2][i] = min(dp[1][i - 1], dp[0][i - 1]) + cost[i][2]
result = min(dp[0][last], dp[1][last], dp[2][last])- 初始值：
dp[0][0] = cost[0][0]
dp[1][0] = cost[0][1]
dp[2][0] = cost[0][2]def minCost(self, costs: List[List[int]]) -> int:
len_costs = len(costs)
last = len_costs - 1
if len_costs == 0:
return 0
dp = [[None for _ in range(len_costs)] for _ in range(3)]
for i in range(3):
dp[i][0] = costs[0][i]
for i in range(1, len_costs):
dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + costs[i][0]
dp[1][i] = min(dp[0][i - 1], dp[2][i - 1]) + costs[i][1]
dp[2][i] = min(dp[1][i - 1], dp[0][i - 1]) + costs[i][2]
return min(dp[0][last], dp[1][last], dp[2][last])翻转字符
链接： https://leetcode.cn/problems/cyJERH/description/
如果一个由 ‘0’ 和 ‘1’ 组成的字符串，是以一些 ‘0’（可能没有 ‘0’）后面跟着一些 ‘1’（也可能没有 ‘1’）的形式组成的，那么该字符串是 单调递增 的。 我们给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 s，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。 返回使 s 单调递增 的最小翻转次数。
示例 1：
输入：s = “00110” 输出：1 解释：我们翻转最后一位得到 00111.
示例 2：
输入：s = “010110” 输出：2 解释：我们翻转得到 011111，或者是 000111。
示例 3：
输入：s = “00011000” 输出：2 解释：我们翻转得到 00000000。
- 分析状态转移方程：
- dp_f: 把当前字符翻转成”0”且符合单调递增条件的最小翻转次数
- dp_g: 把当前字符翻转成”1”且符合单调递增条件的最小翻转次数
dp_f[i] = dp_f[i - 1] if s[i] == "0" else dp_f[i - 1] + 1
dp_g[i] = min(dp_f[i - 1], dp_g[i - 1]) if s[i] == "1" else min(dp_f[i - 1], dp_g[i - 1]) + 1寻找初始值
dp_f[0] = 0 if s[0] == "0" else 1
dp_g[0] = 0 if s[0] == "1" else 1class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
len_s = len(s)
if len_s <= 1:
return 0
f_cache = 0 if s[0] == "0" else 1
g_cache = 0 if s[0] == "1" else 1
dp_f = f_cache
dp_g = g_cache
for i in range(1, len_s):
dp_f = f_cache if s[i] == "0" else f_cache + 1
dp_g = min(g_cache, f_cache) if s[i] == "1" else min(g_cache, f_cache) + 1
f_cache, g_cache = dp_f, dp_g
return min(dp_f, dp_g)
![[LeetCode]动态规划之打家劫舍ⅠⅡⅢ](https://ask.qcloudimg.com/http-save/yehe-6557940/ea176eb4ab5e5114421134e427f77801.png)
腾讯云开发者
