东圃手机网站制作费用,大连 网站,wordpress公众号源码,遵义市在哪里做网站目录
动态规划的概念#xff1a;
解决多阶段决策过程最优化的一种方法
阶段#xff1a;
状态#xff1a;
决策#xff1a;
策略#xff1a;
状态转移方程#xff1a;
适用的基本条件
1.具有相同的子问题
2.满足最优子结构
3.满足无后效性
动态规划的实现方式…目录
动态规划的概念
解决多阶段决策过程最优化的一种方法
阶段
状态
决策
策略
状态转移方程
适用的基本条件
1.具有相同的子问题
2.满足最优子结构
3.满足无后效性
动态规划的实现方式 动态规划的概念
解决多阶段决策过程最优化的一种方法
阶段
把问题分成几个相互联系的有顺序的环节。
状态
某一阶段的出发位置
决策
从某一状态演变到下一个状态的选择
策略
从开始到终点的决策序列。
状态转移方程
从i到i1状态的演变规律。
适用的基本条件
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]为没有上过50f[i][1]为上过50这样的话我们在i50前用f[i][0]f[i-1][0]f[i-2][0]; f[i][1]0;
i50: f[50][0]0,f[50][1]f[49][0]f[48][0],
i50i100: f[i][0]f[i-1][0]f[i-2][0],f[i][1]f[i-1][1]f[i-2][0];
i100:f[100][0]f[99][0]f[98][0],f[100][1]0;
i100: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.记忆化搜索
