DP 状态 DP 转移方程 动态规划解题思路

 

如何学好动态规划（2） 原创 Gene_Liu LeetCode力扣 今天

算法萌新如何学好动态规划（1） https://mp.weixin.qq.com/s/rhyUb7d8IL8UW1IosoE34g

动态规划概述

动态规划（Dynamic Programming），因此常用 DP 指代动态规划。本块内容我们主要讲解「动态规划解题思路」与「动态规划问题类别」。

动态规划解题思路

动态规划主要分为两个核心部分，一是确定「DP 状态」，二是确定「DP 转移方程」。

DP 状态

「DP 状态」的确定主要有两大原则：

1. 最优子结构
2. 无后效性

最优子结构

我们仍以「宝石挑选」例题来讲解这两大原则，首先是「最优子结构」。

什么是「最优子结构」？将原有问题化分为一个个子问题，即为子结构。而对于每一个子问题，其最优值均由「更小规模的子问题的最优值」推导而来，即为最优子结构。

因此「DP 状态」设置之前，需要将原有问题划分为一个个子问题，且需要确保子问题的最优值由「更小规模子问题的最优值」推出，此时子问题的最优值即为「DP 状态」的定义。

例如在「宝石挑选」例题中，原有问题是「最大连续区间和」，子问题是「以 i 为右端点的连续区间和」。并且「以 i 为右端点的最大连续区间和」由「以 i - 1 为右端点的最大连续区间和」推出，此时后者即为更小规模的子问题，因此满足「最优子结构」原则。

由此我们才定义 DP 状态 f[i] 表示子问题的最优值，即「以 i 为右端点的最大连续区间和」。