dp动态规划的基本

在平时刷题的过程中，总会有一些题目让人无法下手，比如什么最长上升子序列，最长公共子序列，01背包…当你去了解它时，你会知道它们叫一个统一的名字 ----动态规划（dp）,这是什么东西？，规划动态的东西？
动态规划到底是何方神圣呢？动态规划算法有什么用呢？这些问题在这篇文章我都会为你解答

dp到底是什么

dp它也就是动态规划英文dynamic programming的缩写而已，当然，它也被叫做状态，什么是状态呢？他就好比你写数学题，解方程设的那个x罢了，在真实的题目中，要用动态规划解题就必须要先设状态，如我设dp[i]为前i项的最长上升子序列，dp[i]为最长上升子序列的长度，如我设dp[i][j]为前i个物品的z重量为j，价值为dp[i][j]…dp的状态各种各样，可以是一维，可以是二维，可以是三维，可以是四维…这就是dp的状态

只有dp就可以了吗？

我能肯定的告诉，不行，这就像你写数学题解方程，x设过了，就不代表你把方程给列出来了，不代表你把他给解出来了。这时，按照解“方程”，我们应该到了列方程了，不过动态规划里的“方程”和解“方程”是同步进行的，称作-----状态转移方程。怎么理解呢？就是我们设的状态他是动态的，而我们平时设的数组是静态的，这俩虽同为数组，却意义不同，这就是为了给现在的状态转移方程铺垫，你想想如果为静态，怎么转移，转移就是转移答案，所以状态转移方程就是用来转移答案的。什么？你问我为什么要转移？那我能说，dp他本身是分成子问题一个一个解的，一个子问题又要再分子问题，所以答案解完后要递归回去，再解决掉，然后再递归回去…重复的去干，这其实是一种动态的转移。

状态转移方程有哪些？

状态转移方程分为递推类，如找规律，数组递推这种，背包问题，这就是要加贪心策略了（贪心+动规等于更贪（doge）），树状类，图论类，区间类…只有你想不到，没有他用不到

动态规划可以解决哪些题？

动态规划其实就是求最值的一种算法，和贪心类似，但贪心解决不了的题动规能解决，前提得有状态，不然就不行

好了基本的东西说完了，最后跟大家再分享下动规的策略吧
1.设状态
2.确定状态转移方程
3.确定答案