活动地址：CSDN21天学习挑战赛

👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟

🏡个人主页：starry陆离

🕒首发日期：2022年8月13日星期六
📚订阅专栏：『算法分析与设计』
🍁每日推荐：牛客网-面试神器

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

---

1.动态规划创始人

动态规划（Dynamic Programming, DP）由 R.Bellman（理查·贝尔曼）教授于1957年提出

Richard Ernest Bellman (1920-1984)，美国数学家，美 国艺术与科学院院士，美国工 程院院士，动态规划的创始人。

2.定义

动态规划是将多阶段决策问题进行公式化的一种技术，它是运筹学的一个分支， 用于求解多阶段决策过程的最优化问题

动态规划方程又称为贝尔曼方程

3.总体思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子 问题

经分解得到的子问题往往不是互相独立的，有些子问题被重复计算多次

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就 可以避免大量重复计算，从而得到多项式时间算法

比如这个之前的4.『递归』整数划分问题就计算了很多的重复子问题，我们可以使用动态规划的方法将子问题的解保存起来，避免计算重复的子问题

4.基本要素

最优子结构

一个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质

分析问题的最优子结构性质：首先假设由问题的最优解导出的子问题的解不是 最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从 而导致矛盾

利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步 构造出整个问题的最优解

最优子结构是一个问题能用动态规划算法求解的前提

重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复 计算多次，这种性质称为子问题的重叠性质

动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当 再次需要解此子问题时，只是简单地用常数时间查看一下结果

5.备忘录法（记忆化搜索）

备忘录方法的控制结构与直接递归方法的控制结构相同

区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避 免相同子问题的重复求解

int solve()
{
    if(备忘录中包含子问题的解) return 备忘录中的值
    else 递归求解
}

1
2
3
4
5
6

int num[n][n];
int q(int n, int m) {
    if((n<1)||(m<1)) return 0;
    if((n==1)||(m==1)) return 1;
    if(n<m) return q(n,n);
    if(n==m) {
        if (num[n-1][n-2]==0) {
        	num[n-1][n-2] = q(n,n-1);
        }
        return 1 + num[n-1][n-2];
    }
    if (n>m) {
        if (num[n-1][m-2]==0) {
            num[n-1][m-2] = q(n,m-1);
        }
        if (num[n-m-1][m-1]==0) {
            num[n-m-1][m-1]=q(n-m,m);
        }
        return num[n-1,m-2] + num[n-m-1][m-1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6.斐波那契数列(备忘录法)

如何设计一个去除重复的求斐波那契数列第n项的算法？

7.数字三角形

经典递归解法

int a[110][110],n;
int solve(int i,int j)
{
    if(i==n+1) return 0;
    return a[i][j]+max(solve(i+1,j),solve(i+1,j+1));
}
……
printf("%d\n",solve(1,1)); //(1,1)到最后一层的最大路径和
1
2
3
4
5
6
7
8

记忆化搜索（备忘录法）

int p[105][105],a[105][105],n;
int solve(int i,int j)
{
    if(p[i][j]>=0) return p[i][j]; //引入备忘录保存子问题的解
    if(i==n+1) return 0;
    return p[i][j]=a[i][j]+max(solve(i+1,j),solve(i+1,j+1));
}
……
memset(p,-1,sizeof(p)); //初始化备忘录
solve(1,1);
printf(“%d\n”,p[1][1]); //p[1][1]即为所求解

1
2
3
4
5
6
7
8
9
10
11
12

动态规划法（T(n)=O(n²))

思路一自底向上求解：p[i][j]表示(i, j)的达到最后一层的最大路径和，那么p[i][j]的最优解 包含了子问题p[i+1][j]或p[i+1][j+1]的最优解

状态转移方程如下：这种思路下最终的答案在p[1][1]中

int p[105][105],a[105][105],n;
int solve()
{
    for(int j=1;j<=n;j++) p[n][j]=a[n][j];
    for(int i=n-1;i>=1;i--) //自底向上DP
    	for(int j=1;j<=i;j++)//对行遍历
    		p[i][j]=a[i][j]+max(p[i+1][j],p[i+1][j+1]);
}
……
solve();
printf("%d\n",p[1][1]);
1
2
3
4
5
6
7
8
9
10
11

思路二自顶向下：p[i][j]表示从(1,1)到达(i, j) 的最大路径和，那么p[i][j]的最优解包 含了子问题p[i-1][j-1]或p[i-1][j]的最优解

状态转移方程如下：这种思路下最终的答案在p[n][j]中

🍁每日推荐：牛客网-面试神器