动态规划入门

uniartisan

发布于 2022-03-02 11:37:55

46300

代码可运行

文章被收录于专栏：uu的自留地uu的自留地

运行总次数：0

代码可运行

五大常用算法：动态规划

引入

1. 基本概念

动态规划英文 Dynamic Programming，是求解决策过程最优化的数学方法，后来沿用到了编程领域。

动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程，从简单的初始状态一步一步递推，最终得到复杂问题的最优解。

动态规划解决问题的过程分为两步：

寻找状态转移方程
利用状态转移方程式自底向上求解问题

找出来以下三点，题目就完成了80%：

状态表示：如何用数组表示实际问题
状态转移：如何由已知状态表示未知状态
状态边界：哪些状态不用转移就可以得到

具有以下三个特性的问题适用于动态规划：

最优子结构：全局最优解包含局部最优解
重叠子问题：子问题出现大量重叠
无后效性：每次决策不影响之后的决策

2. 爬楼梯问题

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

简化题目：

假设这里只有十级台阶，方便于表述。

动态规划思路：

动态规划简单来说就是：大事化小，小事化了。

那这道题目来讲，假设还差最后一步走到第十级台阶，这时候有两种情况：还有 1 级台阶/ 2级台阶。如果暂时不考虑 0~~8 级的过程，也不管 0~~9 级的过程，那么 0~10级的走法就是这两个方法的数值之和。

这时我们不考虑总共的台阶为 10，换为 8/9，我们重新考虑分别走到第八级和第九级的方法。这里我们先假设走到第 N 级台阶的方法为 F(N)： F(10)=F(8)+F(9)

同理：

F(9)=F(8)+F(7)

F(8)=F(7)+F(6)

此时： F(N)=F(N-1)+F(N-2) 是阶段与阶段之间的 状态转移方程

递归实现

int getNumWays(int n)        \\&#x4E8C;&#x53C9;&#x6811;
{
    if (n &lt; 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    else {
        return getNumWays(n - 1) + getNumWays(n - 2);
    }
}

备忘录算法

上面的算法时间复杂度很高，树的结点个数是递归的计算次数。树的高度为 N-1，节点个数接近 2^n-1,时间复杂度为 O(2^n)。

如果用树状图来表示的话，我们可以得到一颗二叉树：

可以看到，重复计算了很多相同的参数输入。我们可以通过数组或者哈希表记录节点值来完成时间复杂度的简化。这里我们用c++中STL来实现：

map &lt;int, int&gt; cache;
int getNumWays(int n)
{
    if (n &lt; 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (cache.count(n)) {
        return cache[n];
    }
    else {
        int value = getNumWays(n - 1) + getNumWays(n - 2);
        cache[n] = value;
        return value;
    }
}

在以上代码中，集合 cache 是一个备忘录。当每次需要计算F(N)的时候，会首先从 cache 中寻找匹配元素。如果存在，就直接返回结果，如果不存在，就计算出结果，存入备忘录中。可以简单得到，这个算法复杂度为 O(N)。

动态规划

虽然到上面一步已经实现了时间复杂度的优化，但还算不上真正的动态规划。前面提到：

动态规划解决问题的过程分为两步：

寻找状态转移方程
利用状态转移方程式自底向上求解问题

我们继续尝试自下而上迭代计算结果，由于每一次步的结果只依赖于之前的两个状态，所以我们只用推导新的状态。

int getNumWays(int n)
{
    if (n &lt; 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int a = 1, b = 2, temp = 0;

    for (int i = 3; i &lt;= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }

    return temp;
}