算法——C/动态规划

一、动态规划基础

什么是DP

DP(动态规划)全称Dynamic Programming,是运筹学的一个分支，是一种将复杂问题分解成很多重叠的子问题，并通进子问题的解得到整个问题的解的眼一种算法在动态规划中有一些概念： 状态：就是形如dp[ i ] [ j ]= val 的噉值，其中i、j为下标，也是用于描述、确定状态所需的变其中val 为状态值。 状态转移：状态与状态之间的转移关系，一般可以表示为一个数学表达式，转移方向决定了迭代或递归方向。 最终状态：也就是题目所求的状态，最后的答案。

分析步骤

1.确定状态，一般为“到第i个为止xx为j(xx为k)的方案数/最小代价/最大价值”，可以根据数据范围和复杂度来推理。

2.确定状态转移方程，即从已知状态得到新状态的方法，并确保按照这个方向一定可以正确地得到最终状态。 根据状态转移的方向来决定使用迭代法还是递归法、记忆法

3.确定最终状态并输出。

数字三角

线性dp、

二维dp、

LIS、

LCS