因为最近在学习强化学习的原因，经常用到动态规划的概念，所以就跳了前面的部分先看这里的动态规划初步，先对这个东西建立一个初步的认识

数字三角形

书中先从一个题目入手阐述动态规划的基本思路和特点，问题描述如下：

有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数：
从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来，如何使得这个和尽量大？

分析：

• 如果用回溯法可以求出所有可能的路线，但是效率太低，一个n层数字三角形的完整路线有2^n-1条

• 把当前的位置(i,j)看成一个状态，定义状态(i,j)的指标函数d(i,j)为从格子(i,j)出发时能得到的最大和(包括格子(i,j)本身的值)，因此在这个定义下，原问题的解是d(1,1)
  每个格子对应的状态如下图所示：
  

• 从格子(i,j)出发有两种决策，如果往左走到(i+1,j)后就变成了求解"从(i+1,j)出发能得到的最大和"这一问题，即d(i+1,j)；往右走就需要求解d(i+1,j+1)，应当选取d(i+1,j)和d(i+1,j+1)中较大的一个，即得到了状态转移方程：

\[d(i,j)=a(i,j)+max[d(i+1,j),d(i+1,j+1)] \]

• 最优子结构：全局最优解包含局部最优解

动态规划的核心是状态和状态转移方程

记忆化搜索与递推

在之前的问题分析中，获得了状态转移方程，接下来就需要用这一方程进行计算

• 递归计算(要注意边界处理)

int solve(int i,int j){
  return a[i][j] + (i == n ? 0 : max(solve(i+1,j),solve(i+1,j+1)));
}

递归运算的缺点在于时间效率太低，因为发生了重复运算，比如solve(3,2)被计算了两次(一次是solve(2,1)需要的，一次是solve(2,2)需要的)，总的算来，如果原来的三角形有n层，则需要计算2ⁿ-1个结点

用直接递归的方法计算状态转移方程，效率往往十分低下，因为相同的子问题被重复计算了多次

• 递推计算

int i, j;
for(j = 1; j <= n; j ++)
  d[n][j]=a[n][j];
for(i = n - 1; i >= 1; i--)
  for(j = 1; j <= i; j ++)  // 第i层就有i个格子
    d[i][j] = a[i][j] + max(d[i+1][j], d[i+1][j+1]);

这样的程序时间复杂度是O(n²)，原理是i是逆序枚举的，在计算d[i][j]前，其所需要的d[i+1][j]和d[i+1][j+1]已经计算出来了

可以用递推法计算状态转移方程，递推的关键在于边界和计算顺序，其时间复杂度是：状态总数每个状态的决策个数决策时间

• 记忆化搜索
  程序分为两部分，首先调用memset(d,-1,sizeof(d));，把d全部初始化为-1，然后编写递归函数：

int solve(int i,int j){
  if(d[i][j] >= 0)
    return d[i][j];
  return d[i][j] = a[i][j] + (i == n ? 0 : max(solve(i+1,j),solve(i+1,j+1)));
}

上述程序采用的方法称为记忆化，把计算结果保存在数组d中，题目中提到各个数都是非负的，因此如果已经计算过某个d[i][j]，则它应该是非负的，因此只需将d初始化为-1，即可通过判断d[i][j]≥0得知其是否被计算过，因此可以保证每个结点只访问一次

采用记忆化搜索时，不必事先确定各状态的计算顺序，但需要记录每个状态是否被计算过

DAG上的动态规划

有向无环图上的动态规划是学习动态规划的基础，很多问题都可以转化为DAG上的最长路、最短路或路径计数问题

DAG模型

• 嵌套矩形问题：有n个矩形，每个矩形可以用两个整数a和b描述，表示它的长和宽，当且仅当a

  • 矩形之间的可嵌套关系是一个典型的二元关系，二元关系可以用图来建模：如果矩形X可以嵌套在Y中，就从X到Y连一条有向边，同时这个有向图是无环的，因为一个矩形无法直接或间接嵌套在自己内部，因此它是一个DAG，问题就转换为求DAG上的最长路径

• 硬币问题：有n种硬币，面值分别为V1，V2，...，Vn，每种都有无限多，给定非负整数S，可以选用多少硬币，使得面值之和恰好为S，输出硬币数目的最小值和最大值(1≤n≤100，0≤S≤10000，1≤Vi≤S)

  • 这个问题的本质也是DAG上的路径问题，将每种面值看作一个点，表示"还需要凑足的面值"，则初始状态为S，目标状态为0，若当前在状态i，每使用一个硬币j，状态就转到i-Vj

• 对比两个问题，有一些不同之处，第一题没有确定路径的起点和终点，而第二题的起点必须是S，终点必须为0，因此点固定的最短路才是有意义的

最长路及其字典序

嵌套矩形问题就是要在DAG中求出不固定起点的最长路径，令d(i)为从结点i出发的最长路长度，第一步只能走到它的相邻点，因此可写出状态转移方程：

\[d(i) = max[d(j) + 1 | (i,j)∈E] \]

其中E为边集，可以采用递推或记忆化搜索的方式计算上式，首先先要把图建立起来，比如用邻接矩阵保存在矩阵G里，然后编写记忆化搜索程序：

int dp(int i){
  int& ans = d[i];    // 为d[i]声明一个引用
  if(ans > 0)
    return ans;
  ans=1;
  for(int j = 1;j <= n;j++)
    if(G[i][j]) ans = max(ans, dp(j) + 1);
  return ans;
}

在记忆化搜索中，可以为正在处理的表项声明一个引用，简化对其的读写操作

原题中还要求在多个最优解当中，矩形编号的字典序最小，因此还需要在所有d值计算出来后，选择最大的d[i]所对应的i，如果有多个i，则选择最小的i，接下来选择d(i) = max[d(j) + 1 | (i,j)∈E]中的最小的j：

int print_ans(int i){
  printf("%d", i);
  for(int j = 1;j <= n;j ++)
    if(G[i][j] && d[i] == d[j] + 1)
    {
       print_ans(j);
       break; 
    }

}

根据各个状态的指标值可以依次确定各个最优决策，从而构造出完整方案，由于决策是依次确定的，所以很容易按照字典序打印出所有方案

固定终点的最长路和最短路

在硬币问题中，考虑最长路径，因为终点是固定的，所以d(i)的确切含义变为"从结点i出发到结点0的最长路径长度"，可编写代码如下：

int dp(int S){
  int& ans = d[S];  
  if(ans >= 0)
    return ans;
  ans = 0;
  for(int i = 1;i <= n;i++)
    if(S >= v[i]) ans = max(ans, dp(S - V[i]) + 1);
  return ans;
}

在本题中，路径长度可以为0(S本身可以为0)，因此不能再用d=0表示这个d值还未计算过，故初始化时要把d设置为一个负值表示为计算过

当程序中需要用到特殊值，应确保该值在正常情况下不会被取到，同时如果用特殊值表示还没算过，必须和其他特殊值(比如无解)区分开

不过上述的程序没有考虑结点S无法到达结点0的特殊情况