DP—线性类动态规划

【概述】由于概率和期望具有线性性质，使得可以在概率和期望之间建立一定的递推关系，这样就可以通过动态规划来解决一些概率问题，例如概率和期望的最值问题就常常使用概率 DP、期望 DP 来解决。

与其他的动态规划一样，合理的选择状态以及高效的状态转移方程是关键，选择合适的状态不仅可以提高效率，而且可以保证动态规划所必须的无后效性。

将问题直接作为状态是最好的，当找到正确的状态定义后，转移是较容易想到的，一般的递推即可一般的递推即可一般来说，将问题直接作为状态确定转移。

确定转移例如：n 个人做 XX 的期望次数，可以设计状态 f[i] 表示 i 个人做完事的期望。

【概率 DP】概率 DP 通常已知初始的状态，然后求解最终达到目标的概率，因此概率 DP 需要顺序求解。

其相较于期望 DP较为简单，当前状态只需加上所有上一状态乘上转移概率即可，即：f[i]=f[i-1]*p[i]【期望 DP】期望 DP 与概率 DP 不同，其需要倒序求解。

当求解达到某一目标的期望花费时，由于最终的花费无从知晓（无法从无穷推起），因此期望 DP 需要倒序求解。

设 f[i] 为 i 状态下实现目标的期望值，即到了 f[i] 这个状态的差距是多少。

初始时，令 f[n]=0，即在目标状态期望值为 0，然后进行状态转移，新的状态为上一状态与转移概率的乘积再加上转移的花费即：f[i-1]=f[i]*p[i]+w最后初始位置 f[0] 即为所求的期望值需要注意的是，当转移关系不成环时，期望 DP 可以进行线性递推，但当转移关系成环时，期望 DP 的最终状态相当于一个已知量，而转移关系相当于一个个方程，此时需要使用高斯消元法来解决。

【例题】Discovering Gold（LightOJ-1030）(期望DP)：点击这里Dice (III)（LightOJ-1248）(期望DP)：点击这里Just another Robbery（LightOJ-1079）(概率DP+01背包)：点击这里Let's Play Osu!（CF-236D）(期望DP)：点击这里Piglet's Birthday（CF-248E）(概率DP)：点击这里Robots（2019 ACM-ICPC 南京赛区网络赛 D）(期望DP)：点击这里Everything Is Generated In Equal Probability（HDU-6595）(期望DP)：点击这里Kejin Player（HDU-6656）(期望DP+降维)：点击这里。

动态规划方法求解线性规划问题1. 线性规划问题简介线性规划是一种常见的数学优化方法，用于求解线性约束条件下的最优解。

它的目标是在给定的约束条件下，找到使目标函数取得最大（或者最小）值的变量取值。

2. 动态规划方法概述动态规划是一种通过将问题分解为子问题并逐步解决的方法。

它适合于具有重叠子问题和最优子结构性质的问题。

对于线性规划问题，动态规划方法可以通过将问题分解为多个子问题，并利用子问题的最优解来求解整体问题的最优解。

3. 动态规划方法求解线性规划问题的步骤步骤1: 定义状态首先，我们需要定义状态变量。

对于线性规划问题，状态变量可以是目标函数的值，或者是满足约束条件的变量取值。

步骤2: 定义状态转移方程接下来，我们需要定义状态之间的转移关系。

对于线性规划问题，状态转移方程可以表示为：dp[i] = max(dp[i-1] + a[i], a[i])其中，dp[i]表示第i个状态的最优值，a[i]表示第i个状态的值。

步骤3: 初始化状态在动态规划方法中，我们需要初始化第一个状态的值。

对于线性规划问题，我们可以将第一个状态的值设置为目标函数的初始值。

步骤4: 递推求解最优解接下来，我们可以使用状态转移方程递推求解最优解。

通过计算每一个状态的最优值，我们可以得到整体问题的最优解。

步骤5: 回溯求解最优解最后，我们可以通过回溯的方式求解最优解的具体取值。

通过追踪每一个状态的转移路径，我们可以找到使目标函数取得最大（或者最小）值的变量取值。

4. 动态规划方法求解线性规划问题的实例为了更好地理解动态规划方法求解线性规划问题的过程，我们来看一个具体的实例。

假设有一个线性规划问题，目标是最大化目标函数：maximize 3x + 4y约束条件为：2x + y <= 10x + 3y <= 15x, y >= 0我们可以按照以下步骤使用动态规划方法求解该线性规划问题：步骤1: 定义状态我们定义状态变量为目标函数的值，即dp[i]表示目标函数的值为i时的最优解。

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状 态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化 问题的方法为动态规划方法 。
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适 用动态规划的问题必须满足最优化原理和无后效性 。
动态规划
运筹学的分支
01 原理
03 局限性
目录
02 分类
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年 代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理， 从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域， 并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了 显著的效果 。
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成 的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足 最优化原理又称其具有最优子结构性质 。
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来 的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又 称为无后效性 。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因 素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点 。

dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
}
}
i\j
j=0
i=0
0
j=1 j=2 j=3 j=4 j=5 j=6
0
00000i=10
3
6
9
12 15 18
i=2
0
3
6
10
13 16 20
17
多重背包
有n种物品，每种最多可以取x[i]个，每个物品有大小和价值，问总大小不超过m的情况下能取到最大的 价值是多少 代码如下： for (int i = 1; i <= n; ++i) {
} } 注意此时j一定是倒序产生
16
完全背包
有n种物品，每种最多可以取无数个，每个物品有大小和价值，问总大小不超过m的情况下能取到最大 的价值是多少
01背包中第二维改成正向即可：
for (int i = 1; i <= n; ++i) {
for (int j = c[i]; j <= m; ++j) {
}
10
数字三角形
线性DP解法 for(int i=m-1;i>0;i--) {
for(int j=0;j<=i;j++) { a[i-1][j]+=max(a[i][j],a[i][j+1]);
} }
11
数字三角形
暴力递归搜索解法： int dfs(int i, int j) {
if (i == n) return a[i][j]; return max(dfs(i+1,j), dfs(i+1,j+1)) + a[i][j]; }