动态规划的题有多少类型？

来源：百度知道 编辑：UC知道 时间：2024/06/06 20:35:37
我会一点动态规划，但不知道它的题有多少类型
比如矩阵连乘是一种，最短路径问题又是一种。
我想请教一下大概有多少种，各是什么，代表的题是什么。
谢谢

动态规划问题可以有tD/eD的形式，n^t为问题的大小，n^e为问题所依赖的子问题的大小
1D/1D型，最长上升子序列
2D/0D型，最长公共子序列
2D/1D型，多源最短路径
2D/2D型，双背包问题
当然可以有3D/1D或者更高的。

动态规划题目千变万化，主要是要学会思考方法，要能看到题目很快找出题目中的状态，找准状态后就基本没有难度了