数据结构(十二)动态规划

╰半夏微凉° 2022-05-31 07:27 152阅读 0赞

### **1 递归函数建模** ###

动态规划一般用于全局问题，在构造递归的时候，一般采用自顶向下分解的方法，先把全局问题分解成更小的子问题求解。下面举两个例子

**例子1：**有一座高度是10阶的楼梯，从下往上走，每跨一步可以是一级或两级台阶。要求用程序求出一共一共有多少种走法。

**问题分析建模**：首先总共有10步，假设只剩最后一步就到达第10阶，这个时候会有两种情况：第一种是从第九阶到第十阶，第二种是从第八阶到第十阶,然后两种情况里面如何从第一个阶梯走到第九阶，从第一个阶梯走到第八阶。也就是我们可以构造出最后一步的函数：

f(10)=f(9)+f(8)

这个时候我们就可以构造出递归函数：

f(n)=f(n-1)+f(n-2)

写成通用一点的公式，也就是用for循环遍历最后一次的情况：

f(n)=sum(f(n-j)) 且j=1,2

因此我们只要知道初始值f(1)、f(2)就可以求解f(10)。这种我们称之为一维动态规划。

**例子**2：给定一个m\*n矩阵A，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的矩阵如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12。

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

**问题分析建模**：对于这个题目，假设m是m行n列的矩阵，那么我们用dist\[m\]\[n\]来抽象这个问题，dist\[i\]\[j\]表示的是从原点到i,j位置的最短路径和。我们要求解的是dist\[m\]\[n\]的最大值,然而其实最后一步dist\[m\]\[n\]又可以分解成两种情况，从dist\[m-1\]\[n\]往下走；从dist\[m\]\[n-1\]往右走，取这两种情况的最小值，那么我们就可以列出方程：

dist\[m\]\[n\]=min(dist\[m-1\]\[n\]+A\[m\]\[n\],dist\[m\]\[n-1\]+A\[m\]\[n\])

抽取出A\[m\]\[n\]，该方程可以进一步写成：

dist\[m\]\[n\]=A\[m\]\[n\]+min(dist\[m-1\]\[n\],dist\[m\]\[n-1\])

因此接着我们只需要根据初始条件，就可以求解，初始条件dist\[0\]\[0\]=1。这个例子又称之为二维动态规划。

### **2动态规划** ###

#### **(1)自顶向下递归** ####

其主要原理是加入备忘录，用于记录之前已经记录过的函数值，比如在写例子1递归函数：

f(n)=f(n-1)+f(n-2)

代码的时候，用一个数组记录一下f(i),然后在写递归函数的时候，遇到f(i)的值如果已经被计算过一次了，那么就不用继续计算了；如果还没有被记录，那么就保存一下f(i)。

在写例子2递归函数的时候，用二维的数组f\[m\]\[n\]记录一下已经计算过的函数值

#### **(2)自底向上迭代** ####

从0开始往上迭代，比如对于例子1，先求：

f\[2\]=f\[1\]+f\[0\]

f\[3\]=f\[2\]+f\[1\]

f\[4\]=f\[3\]+f\[3\]

直到迭代到f\[10\]为止。

### **3 示例源码** ###

#include <istream>;
    #include <vector>;
    #include <math.h>
    using namespace std;
    int A[4][4] = {1,3,5,9,8,1,3,4,5,0,6,1,8,8,4,0};
    int f[4][4]={0};//备忘录
    int count=0;//统一一下采用备忘录的时候，减少的计算次数
    int function_top2bottom(int m,int n){//自顶向下递归
        if (f[m][n]>0)
            return f[m][n];
        count++;
    
        int min_dist=0;
        if(m==0&&n==0)
        {
            min_dist=0;
        }
        else if (m-1>=0&&n==0)
            min_dist=function_top2bottom(m-1,n);
        else if (m==0&&n-1>=0) {
            min_dist=function_top2bottom(m,n-1);
        }
        else {
            min_dist=min(function_top2bottom(m,n-1),function_top2bottom(m-1,n));
        }
        f[m][n]=min_dist+A[m][n];
    
        return f[m][n];
    }
    
    int function_bottom2top(int m,int n){//自底向下迭代
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j <n ; ++j) {
                int min_dist=0;
                if(m==0&&n==0)
                {
                    min_dist=0;
                }
                else if (m-1>=0&&n==0)
                    min_dist=f[m-1][n];
                else if (m==0&&n-1>=0) {
                    min_dist=f[m][n-1];
                }
                else {
                    min_dist=min(f[m-1][n],f[m][n-1]);
                }
                f[m][n]=min_dist+A[m][n];
            }
    
        }
    
    
        return f[m][n];
    }
    
    void dynamic_programming()
    {
    
        std::cout<<function_top2bottom(3,3)<<std::endl;
        std::cout<<count<<std::endl;//可以测试一下，自顶向下递归的时候，少用备忘录的count值
    
        std::cout<<function_bottom2top(3,3)<<std::endl;
    
    }