dynamic-programming-basis

动态规划基础

动态规划定义

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

DP的原理介绍

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

概念引入

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

基本概念

多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。

动态规划问题中的术语

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点 。

无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
决策变量的范围称为允许决策集合。
策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。

允许策略集合中达到最优效果的策略称为最优策略。

给定 k 阶段状态变量 x(k) 的值后，如果这一阶段的决策变量一经确定，第 k+1 阶段的状态变量 x(k+1) 也就完全确定，即 x(k+1) 的值随 x(k) 和第 k 阶段的决策 u(k) 的值变化而变化，那么可以把这一关系看成 (x(k),u(k)) 与 x(k+1) 确定的对应关系，用 $x(k+1)=Tk(x(k),u(k)) $表示。这是从 k 阶段到 k+1 阶段的状态转移规律，称为状态转移方程。

最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。
最优性原理实际上是要求问题的最优策略的子策略也是最优。

基本结构

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理（最优子结构性质）

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

子问题的重叠性

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

动态规划解题套路

首先是一个解释非常好的链接： 告别动态规划，连刷40道动规算法题，我总结了动规的套路

动态规划的三个步骤

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 $dp[]$ 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 $dp[i]$ 是代表什么意思？

第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 $dp[n]$ 时，是可以利用 $dp[n-1]$，$dp[n-2]$……$dp[1]$，来推出 $dp[n]$ 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 $dp[n] = dp[n-1] + dp[n-2]$，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

学过动态规划的可能都经常听到最优子结构，把大的问题拆分成小的问题，说时候，最开始的时候，我是对最优子结构一梦懵逼的。估计你们也听多了，所以这一次，我将换一种形式来讲，不再是各种子问题，各种最优子结构。所以大佬可别喷我再乱讲，因为我说了，这是我自己平时做题的套路。

第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 $dp[n] = dp[n-1] + dp[n-2]$，我们可以通过 $dp[n-1]$ 和$ dp[n-2]$ 来计算 $dp[n]$，但是，我们得知道初始值啊，例如一直推下去的话，会由 $dp[3] = dp[2] + dp[1]$。而 $dp[2]$ 和 $dp[1]$ 是不能再分解的了，所以我们必须要能够直接获得 $dp[2]$ 和 $dp[1]$ 的值，而这，就是所谓的初始值。

由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 $dp[n]$ 的值了，而 $dp[n]$ 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

dp经典实例——三种背包问题

滚动数组

滚动数组简单的理解就是让数组滚动起来，起到节省存储空间的作用。主要应用在递推或动态规划中。

举个适合使用滚动数组的例子:
斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和。
递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。
假如我们要求斐波拉切数列的第80项，我们常规的方法是定义一个80大小的数组，然后进行如下的循环。

for (int i = 2; i < 80; i++) {
	d[i] = d[i - 1] + d[i - 2];
}

那么我们要求第2e7项的斐波拉契，我们不可能去定义一个2e7的数组。通过观察，我们可以发现其实每一次循环都只用到前两位的数组，使用过后就不会使用了，很浪费空间。我们可以使用滚动数组来解决。
使用滚动数组的话，我们就只需要定义一个3大小的数组(仔细想想我们滚动话只需要3个数就够了)。

for (int i = 2; i < 80; i++) {
	d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
}

滚动数组只能节约空间复杂度，时间复杂度还是和原来一样。

(1).01背包

描述:

有n件物品和一个容量为m的背包。第i件物品的费用是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

状态转移方程:

用 $dp[i][j]$表示前i种物品放入一个容量为j的背包的最大价值
$dp[i][j]=j<w[i]? dp[i-1][j]:max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); (1<=i<=n,0<=j<=m)$

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (j < w[i]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
}

此时我们可以发现我们得到了这么一个数组，$dp[i][j]$即表示在前i个物品中选取任意物品装填承重j背包时可得到的最大价值和。

滚动数组

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        dp[i % 2][j] = dp[(i - 1) % 2][j];
        if (j > v[i]) {
            dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - v[i]] + w[i]);
        }
    }
}

但是仅仅滚动数组的优化通常来说是不够的。毕竟不管怎么样还是一个二维数组，优化始终是有限的。

优化版

用$dp[j]$表示当前总重量为j的所有方案中的最大价值
$dp[j]=max(dp[j],dp[j-w[i]]+v[i]); (1<=i<=n ,w[i]<=j<=W)$

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[k - w[i]] + v[i]);
    }
}

这里的一维数组的优化是最优的。

核心是基于一维数组做反向迭代，这样的话j<w[i]的部分直接不用复制了，且由于是反向的线性更新也不会发生冲突。

(2).完全背包

描述:

N种物品，第i种的物品重量是w[i],价值是v[i]，每种物品有无限件，求总重量在背包承重m以内的最大总价值。

状态转移方程:

二维数组
用$dp[i][j]$表示前i种物品放入一个容量为j的背包的最大价值类似于简化为01背包。
$dp[i][j] = max(dp[i][j], dp[i-1][j-kw[i]] + kv[i]]) (1<=i<=n,0<=j<=m) (0 <= k*w[i] <= j)$

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k * w[i] <= j; k++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
        }
    }
}

这里可以理解为变相的01背包，重量为kw[i],价值为kv[i]。

小优化版:用$dp[i][j]$表示前i种物品放入一个容量为j的背包的最大价值,
$dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]+v[i]) (1<=i<=n,0<=j<=W)$

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (j < w[i]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
        }
    }
}

核心在于将已装载的$dp[i][j]$用于后续dp，因为物品无限件，同一物品可以选取多次。这是其与01背包的主要区别。

01背包 $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$;
完全背包 $dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])$;

这个已装载怎么理解？
举个例子:
遍历到第5个物品，其重量是3：
那么$dp[5][3]$处在此次迭代中会存: 以3容量的背包选取前4种物品 和 选取一个桃子后以0容量的背包选取前四种物品中的最优情况。$dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])$;

如果此时选择第5个的情况是最优情况，被存储了，那就表示已装载。因为能在后续的遍历中多次拿到第5个物品。

如果已经$dp[5][3]$拿到了第5个物品那么在后续的$dp[5][6]$只需要存: 以6容量的背包选取前4种物品 和 再拿一个第5个物品加上$dp[5][3]$中的最优情况。

看一下和01背包的区别
在01背包中：
假如遍历到第5个物品，其重量是3：
那么$dp[5][3]$在此处迭代会存:以3容量的背包选取前4种物品 和 选取一个桃子后以0容量的背包选取前四种物品中的最优情况。$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);$
而$dp[5][6]$则是存以6容量的背包选取前4种物品 和 (以3容量的背包选取前4种物品+一个第5中物品的价值)的最优情况。
$dp[5][6]$与$dp[5][3]$没有直接的迭代关系。

滚动数组

完全背包的滚动数组和01背包类似。

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (j < w[i]) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
        } else {
            dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - w[i]] + v[i]);
        }
    }
}

但是仅仅滚动数组的优化通常来说是不够的。

优化版

用$dp[j]$表示当前总重量为j的所有方案中的最大价值
$dp[j]=max(dp[j],dp[j-w[i]]+v[i]); (1<=i<=n,0<=j<=W)$

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

核心在于类似01背包的反向迭代

(3).多重背包

描述

有n种物品，第i种物品的重量是w[i],价值是w[i],每种物品的数量有限k[i],如何在m重量内，让总价值尽可能最大。

普通的二维解法和完全背包很类似。
代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        for (int l = 0; l * w[i] <= j && l <= k[i]; l++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - l * w[i]] + l * v[i]);
        }
    }
}

这里与完全背包唯一不同的就是不但要满足背包大小，还要满足物品个数。

滚动数组

滚动数组多重背包

代码解析:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        for (int l = 0; l * w[i] <= j && l <= k[i]; l++) {
            dp[i % 2][j] =
                max(dp[i % 2][j], dp[(i - 1) % 2][j - l * w[i]] + l * v[i]);
        }
    }
}

(4).二进制优化

这里三个for循环复杂度太高，不适合很多题目，我们要进行优化。

首先我们要知道我们的目的是什么，目的是将单种物品分解为概念上的多个不同物品然后做01背包。而且分解不是乱分解的，我们需要做到首先不能重复，其次需要将所有的分解的情况都要表示出来，比如有10个x物品，我们需要把0-10的组合情况全部都能表示出来。

优化解法 (二进制优化)

1.如果限制的数量物品容量>=当前最大容量
直接考虑成完全背包问题来处理，把物品数量当成无限数量来考虑。

2.如果限制的数量物品容量<当前最大容量
将单种物品二进制分解为概念上的多个不同物品然后做01背包

普通情况直接完全背包很好理解，特殊的二进制分解我们可以根据例子来理解:

假如给了我们 价值为 2，但是数量却是10 的物品，我们应该把10给拆开，要知道二进制能够表示任何数的，所以10 就是可以有1,2,4,8之内的数把它组成，一开始我们选上 1了，然后让10-1=9，再选上2，9-2=7，在选上 4，7-4=3，而这时的3<8了，所以我们就是可以得出 10由 1,2,4,3来组成。

我们能发现1,2,3,4能组成1-10以内的任何数。

那么他们的价值是什么呢，是2,4,6,8，也就说给我们的价值为2，数量是10的这批货物，已经转化成了价值分别是2,4,6,8元的货物了，那么最后在进行dp选择的时候，就能通过他们的最优解选择，组成出我们需要的组成物品。形成概念上的01背包。

for (int i = 1; i <= n; i++) {
    if (k[i] * w[i] >= m) {//直接完全背包
        for (int j = w[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    } else {//二进制分解成不同数量组成的物品，然后01背包
        int tk = k[i];
        int k = 1;
        while (k <= tk) {
            for (int j = m; j >= k * w[i]; j--) {
                dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
            }
            tk -= k;
            k <<= 1;
        }
        if (tk) {
            for (int j = m; j >= k * w[i]; j--) {
                dp[j] = max(dp[j], dp[j - tk * w[i]] + tk * v[i]);
            }
        }   
    }
}