算法--动态规划

思想

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

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

概念

一个模型三个特征：

多阶段决策最优解模型
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.
最优子结构
一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

思路

状态转移表法
状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。
思路大致可以概括为：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题- 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。
状态转移方程法
状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。据最优子结构，写出递归公式，也就是所谓的状态转移方程。状态转移方程的一般形式：
一般形式： U：状态； X：策略
顺推：f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]} 其中， L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk的费用，初始f[U1]；结果：f[Un]。
倒推：
　　f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}
　　L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1 的费用
　　初始f[Un]；结果：f(U1)
思路大致可以概括为：找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

过程

确定问题的决策对象
对决策过程划分阶段
对各阶段确定状态变量
根据状态变量确定费用函数和目标函数
建立各阶段状态变量的转移过程，确定状态转移方程

实际应用

最短路径
最长公共子串长度

示例应用

0-1背包

/**
 * 计算背包最大承载重量
 * 使用二维数组，存储各阶段的状态集合
 *
 * @param items 物品数组
 * @param n     物品个数
 * @param w     背包可承载重量
 * @return 实际背包承载重量
 */
public int compute(int[] items, int n, int w) {
    // 二维数组，初始值都为false
    boolean[][] states = new boolean[n][w + 1];
    // 第一行的数据要特殊处理，可以利用哨兵优化
    states[0][0] = true;

    // 如果第一个物品的重量小于w，就放进背包
    if (items[0] <= w) {
        states[0][items[0]] = true;
    }

    // 动态规划状态转移
    for (int i = 1; i < n; ++i) {
        // 不把第i个物品放入背包
        for (int j = 0; j <= w; ++j) {
            if (states[i - 1][j]) {
                // 此时的状态等于前一个阶段的状态
                states[i][j] = states[i - 1][j];
            }
        }

        // 把第i个物品放入背包
        // j <= w - weight[i]：保证背包重量不会超出
        for (int j = 0; j <= w - items[i]; ++j) {
            if (states[i - 1][j]) {
                states[i][j + items[i]] = true;
            }
        }
    }

    // 输出结果
    for (int i = w; i >= 0; --i) {
        if (states[n - 1][i]) {
            return i;
        }
    }

    return 0;
}

/**
 * 计算背包最大承载重量
 * 使用一维数组，只保存当前阶段的状态集合
 *
 * @param items 物品数组
 * @param n     物品个数
 * @param w     背包可承载重量
 * @return 实际背包承载重量
 */
public int compute2(int[] items, int n, int w) {
    // 一维数组，初始值都为false
    boolean[] states = new boolean[w + 1];
    // 第一行的数据要特殊处理，可以利用哨兵优化
    states[0] = true;

    // 如果第一个物品的重量小于w，就放进背包
    if (items[0] <= w) {
        states[items[0]] = true;
    }

    // 动态规划
    for (int i = 1; i < n; ++i) {
        // 把第 i 个物品放入背包
        // j从大到小循环，保证不会重复
        for (int j = w - items[i]; j >= 0; --j) {
            if (states[j]) {
                states[j + items[i]] = true;
            }
        }
    }

    // 输出结果
    for (int i = w; i >= 0; --i) {
        if (states[i]) {
            return i;
        }
    }
    return 0;
}

/**
 * 计算背包最大承载重量，同时保证相同重量下价值最大
 * 使用二维数组，存储各阶段的状态集合
 *
 * @param items 物品重量数组
 * @param values 物品价格数组
 * @param n     物品个数
 * @param w     背包可承载重量
 * @return 实际背包承载重量
 */
public int compute3(int[] items, int[] values, int n, int w) {
    int[][] states = new int[n][w+1];

    // 初始化 states
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < w+1; ++j) {
            states[i][j] = -1;
        }
    }

    // 第一行的数据要特殊处理
    states[0][0] = 0;

    // 如果第一个物品的重量小于w，就放进背包
    if (items[0] <= w) {
        states[0][items[0]] = values[0];
    }

    // 动态规划，状态转移
    for (int i = 1; i < n; ++i) {
        // 不选择第i个物品
        for (int j = 0; j <= w; ++j) {
            if (states[i-1][j] >= 0) {
                // 此时的状态等于前一个阶段的状态
                states[i][j] = states[i-1][j];
            }
        }

        // 选择第i个物品
        for (int j = 0; j <= w-items[i]; ++j) {
            if (states[i-1][j] >= 0) {
                int v = states[i-1][j] + values[i];
                // 只存储最大值
                if (v > states[i][j+items[i]]) {
                    states[i][j+items[i]] = v;
                }
            }
        }
    }

    // 找出最大值
    int maxvalue = -1;
    for (int j = 0; j <= w; ++j) {
        if (states[n-1][j] > maxvalue) {
            maxvalue = states[n-1][j];
        }
    }

    return maxvalue;
}

最短路径

假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短短路径长度是多少呢？

回溯算法

private int minDist = Integer.MAX_VALUE;
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
    // 到达了 n-1, n-1 这个位置了
    if (i == n && j == n) {
        if (dist < minDist) {
            minDist = dist;
        }
        return;
    }
    if (i < n) {
        // 往下走，更新 i=i+1, j=j
        minDistBT(i + 1, j, dist+w[i][j], w, n);
    }
    if (j < n) {
        // 往右走，更新 i=i, j=j+1
        minDistBT(i, j+1, dist+w[i][j], w, n);
    }
}

动态规划-状态转移表法
从前往后计算各阶段状态：

public int minDistDP(int[][] matrix, int n) {
    // 定义二维状态表
    int[][] states = new int[n][n];

    // 初始化states的第一行数据
    int sum = 0;
    for (int j = 0; j < n; ++j) {
        sum += matrix[0][j];
        states[0][j] = sum;
    }

    // 初始化states的第一列数据
    sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += matrix[i][0];
        states[i][0] = sum;
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            // 状态方程
            states[i][j] = matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
        }
    }
    return states[n-1][n-1];
}

动态规划-状态转移方程法
从后往前迭代递推前阶段的状态：

private int[][] matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
private int[][] mem = new int[4][4];

public int minDist(int i, int j) {
    // 终止条件
    if (i == 0 && j == 0) {
        return matrix[0][0];
    }

    // 如果计算过，直接返回
    if (mem[i][j] > 0) {
        return mem[i][j];
    }

    // 可能1：由左边到当前步骤
    int minLeft = Integer.MAX_VALUE;
    if (j - 1 >= 0) {
        minLeft = minDist(i, j - 1);
    }

    // 可能2：由上面到当前步骤
    int minUp = Integer.MAX_VALUE;
    if (i - 1 >= 0) {
        minUp = minDist(i - 1, j);
    }

    // 状态方程：取两种可能的最小值
    int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
    mem[i][j] = currMinDist;
    return currMinDist;
}

实现问题

算法实现是比较好考虑的。但有时也会遇到一些问题，而使算法难以实现。动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题。
一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因问题而异，进行分析。另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的，而且处理速度也有一些提高。但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做，在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时，是很有意义的。

思想

概念

思路

过程

分类

实际应用

示例应用

0-1背包

最短路径

实现问题