备战蓝桥杯---动态规划（理论基础）

目录

动态规划的概念：

解决多阶段决策过程最优化的一种方法

阶段：

状态：

决策：

策略：

状态转移方程：

适用的基本条件

1.具有相同的子问题

2.满足最优子结构

3.满足无后效性

动态规划的实现方式：

---

动态规划的概念：

解决多阶段决策过程最优化的一种方法

阶段：

把问题分成几个相互联系的有顺序的环节。

状态：

某一阶段的出发位置

决策：

从某一状态演变到下一个状态的选择

策略：

从开始到终点的决策序列。

状态转移方程：

从i到i+1状态的演变规律。

适用的基本条件

1.具有相同的子问题

（1）保证这个问题可以分解成几个子问题并且可以用他们来解决这个问题。

（2）这些子问题也可以分解成相同的子问题。

2.满足最优子结构

问题的最优解包含着他的子问题的最优解，即此后决策必须基于上一次产生的最优决策。

举个栗子：

假如A是当前的最优策略，那么，我们要保证下一次的最优解一定是在A的基础上产生的，而不能是由当前的不是最优的策略导出的。

其实，动态规划是一种分阶段贪心的过程，我们要确保最长远的利益来自于每一步当前的最优利益。

就像这一题，我们选一个路径使他们的和%4最小，显然，如果我们只求当前%4的最小值，无法推出来下一步的最优解。

像这样的情况，我们可以重新考虑状态转移方程，我们发现，每一个余数都有存在的价值，于是我们可以把存在的余数记下来，再用他们去求下一个状态。

3.满足无后效性

要包含所有影响答案的因素，即它用于解决当前问题与过去状态无关的问题

举个例子：

大家应该都写过走楼梯的递归问题。a[i]=a[i-1]+a[i-2]。但是，如果有这么一个规定：走过50楼的人不能再走100楼，显然这样子在100楼时，我们不知道前面的99与98是否走过。

于是，我们应该再记录一个值表示是否踏过50，

我们不妨记f[i][0]为没有上过50，f[i][1]为上过50，这样的话，我们在i<50前用f[i][0]=f[i-1][0]+f[i-2][0]; f[i][1]=0;

i==50: f[50][0]=0,f[50][1]=f[49][0]+f[48][0],

i>50&&i<100: f[i][0]=f[i-1][0]+f[i-2][0],f[i][1]=f[i-1][1]+f[i-2][0];

i==100:f[100][0]=f[99][0]+f[98][0],f[100][1]=0;

i>100:f[i][0]=f[i-1][0]+f[i-2][0];f[i][1]=f[i-1][0]+f[i-2][0];

动态规划的实现方式：

1.递推（直接用for循环）

2.记忆化搜索