第一次了解动态规划算法是在北大郭炜老师的算法课上。当时只是理解了动态规划算法的优越性主要是其尽可能地避免了问题求解过程中地重复运算。只是没想到后来遇到的一个工程问题（关于最小燃油消耗目标下的功率分配）中，可以运用动态规划算法进行求解。

动态规划介绍

————————————————————————
首先简述一下动态规划算法中的思路，以及其是如何避免了求解过程中的重复运算。

上图代表了一个简单的问题，图中的箭头代表我可以选择的路径，假设每抵达一个圆就要花费上面所写的相应的数字，如果我想从起点走到终点，即我需要走四步，那我该如何安排我前三步的走法，使我到达终点时总花费最小呢。

这个问题比较简单，可能一眼就能看出来，那如果是个复杂的问题的话，那就只能通过运算得到了。

如果是要穷举的话（这是最不需要动脑的一种算法了），就这个简单的问题，那大概需要计算：
69+36+75+10=…
69+36+69+10=…
……
……
88+36+75+10=…
88+36+69+10=…
……
……

然后比较出总花费最小的那一个，即为我们的路径。

通过这个举例，我们发现实际上在穷举过程中，包含了很多相同的计算比如69+36+75+10和88+36+75+10二者都包含了36+75+10这个运算，当然肯定还有许多运算都包含了36+69+10这个运算。这说明，在整个计算过程中有很多相同的运算都被重复计算了。

而动态规划算法，就是要避开这些重复的计算。

这个图用动态规划算法怎么算呢？

倒着算。首先算出最后一步到终点的花费。最后一步，不管你在哪个圆上，你都要迈上终点，即花费10。即我们计算出了最后一步各个圆到终点的最小花费是min_cost3=[10 10 10]。保存该值。

然后是倒数第二步，倒数第二步就不一样了，我们有很多路可以选，如果站在36上，你可以迈向75，也可以迈向69；如果站在92上，那可以迈向75、69和66。

我们可以挨着计算，首先，如果我们站在36上，那我们可以迈向75，而从75到终点的min_cost3(1)=10我们已经计算并保存起来了，即目前这条路的cost=75+10=85；同样，我们可以计算出从36迈向69最终到终点的cost为69+min_cost3(2)=69+10=79。

好了目前我们把站在36上的情况已经计算完毕了，那现在我们可以得出一个结论了，如果在倒数第二步时，我们站在了36上，那我们到终点最小的花费应该是min_cost2(1)=min(85,79)=79。

那如果我们站在了92上呢，在92上我又三条路可以走，而这三条路到终点的最小cost应该为min_cost2(2)=76；

同理如果站在77上那最短的路min_cost2(3)=76；

即第二步到终点的最小花费为min_cost2=[79 76 76]；

接下来我们要计算第二步也就是倒数第三步了，同样地，如果我们站在69的位置，我们的两种选择在这一步的花费分别为36和92，而从36和92到终点的最小花费我们已经计算并且存储分别为min_cost2(1)=79和min_cost2(2)=76；

即这两条路的总花费分别为36+79=115和92+76=168.比较起来，站在36的位置，最小的花费应该是115。即min_cost1(1)=115。同样可计算min_cost1(2)=115, min_cost1(3)=153。即min_cost1=[115 115 153]。

现在可以计算第一步了，第一步有三种选择，而这每种选择其到终点的最小花费已经计算完毕了，也就是只需要计算69+min_cost1(1)、69+min_cost1(2)、69+min_cost1(3)。

取这三个结果的最小值。即最终的min_cost=183。在每一步计算时都把该步的最终选择标注一下，即可得到该最小花费所需要的路径，如下图所示。

在这整个过程中，任意一个状态点到终点的最小cost都得到了计算并且将结果进行存储，在下一步计算的时候可以直接调用存储结果，这样可以降低了计算规模与计算量。

如何用动态规划解决工程问题

————————————————————————
对于工程问题，如果该工程问题的状态值可以离散，输入也可以离散，每一步的cost也可求，对于cost的计算也很明确的话，那该工程问题就可以针对cost通过动态规划优化出最佳路径。

首先第一点，确定优化的目标是什么，最小的油耗？最近的路程？最短的时间？这个概念也就是上题中提到过的花费cost。

那第二点，需要明确该问题的状态是什么，而该状态的起点和终点又是什么。

如果研究的对象是电池的话，根据电池模型的建模的不同，状态值大概有SoC、v1等等状态量。不过我觉得状态量的确定应该是根据cost的计算需求确定的。比如计算cost的时候，需要根据目前的状态来计算，但是实际上由于动态规划算法本身是一个倒序的过程，并不能按照状态方程的方式正序计算。所以期间的状态值需要在一定程度上的合理范围内离散成上题中那一个个“圆”，根据所选择的路径、计算从一个圆到下一步的“圆”再到终点的cost。

第三点也就是第二点后面提到的，关于路径。在上一题中，可选择的路径已经确定好了，从上一个状态如何进入到下一个状态，有的是可以有三条路、而有的只能是两条。在实际的问题中，路径不可能是无限的，也就是在一个时间步长内，状态的转移自然是有限度的，仍旧拿电池举例，一块电池在1s的时间步长内，充放电的最大电流为10A，则soc只能在正负10A·s/Capability范围内波动。如果把-10到+10离散成101个点，则对于每个状态点路径可选择的范围就只有101条。

第四点是关于实际的工程问题大都是连续的，需要将连续问题离散化，所有的状态都要离散、“路径”也要离散、而计算cost的时候由于根据路径走到的下一步的状态非常有可能不是刚好落在“圆”上，所也以需要插值。所以一般来说离散间距越小计算越精确、不过也会同时带来计算时间过长的问题。常常要平衡二者，如果是始用matlab编写代码的话，还需要优化代码、启用并行运算等，缩短计算时间。对于非单一状态值的问题，这样每个时间点上得到的就不是状态向量而是状态平面了。这个时候如果想用parfor开启并行运算，就需要将双for转成单for：

for i=1:row
    for j=1:col
	~
	end
end

转为：

parfor m=1:(row*col)
    i=floor((m-1)/col)+1;
    j=mod(m-1,col)+1;
	~
end

如果是用matlab编写伪代码的话，大概是这样的：

初始化所需参数;
for k=时间终点-1:步长:1
	for i=1:状态离散长度
		对于当前状态值，计算不同当前可选择路径下到达的下一状态值和需要的cost;
		对于上述计算的不同路径下达到的下一状态值，插值得到该状态到终点的min_cost;
		当前状态到终点的最小cost=min(各个路径(当前状态到下一状态的cost+下一状态到终点的最小cost));
		记录上述当前状态到终点最小cost所选择的路径;
	end
end
for k=1:步长:时间终点-1
	插值得到该状态点到下一状态点的最佳路径;
	根据路径计算下一状态点;
    根据路径与状态计算cost;
end
~