动态规划篇一：初见动态规划

逃离我推掉我的手 2021-12-23 14:11 331阅读 0赞

# 初见动态规划 #

## 一. 动态规划概念 ##

当年学习算法的动态规划部分时，就觉得一个字，**难**。至今过去一年左右，再次捡起来。  
它可以说是算法的精髓，少了它便少了一份美。而它确实是独一无二的存在，它不属于也不是一个特定的算法，而是一个思想，一种手段。

接下来我们举个例子说明下什么叫**动态规划**，理解下**状态**和**状态转移方程**，理解下**最优子结构**。

**数字三角形**  
![1084440-20190315122411826-721605733.png][]  
如果我们要求从第一行开始，每次往下走一格，可以往左，也可以往右，直到走到最下行，把沿途经过的数全部加起来，如何走才能使得这个数尽量大？  
**解法**

> 把当前的位置(i,j)看成是一种**状态**，然后定位(i,j)的指标函数d(i,j)为从格子(i,j)出发时能得到的最大和(包括自身的值)，这样题目要求就转化成求d(1,1)。

**状态转移方程**：d(i,j)=a(i,j)+max\{d(i+1,j),d(i+1,j+1)\}

**最优子结构**：(i,j)接下来如果往左走，那么就是a(i,j)加上从(i+1,j)位置出发的最大总和，注意这里必须要求(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)));
    }

**解释**

1.  首先该指出此方法不好，时间效率太低，原因在于重复计算。
2.  本程序用到了一个三目运算符，旨在区别最后一行与其他行的运算区别，最后一行就是本身状态值就是了。

### 方法2：递推 ###

伪代码如下

1. 初始化状态值：d[i][j]=a[i][j];
    2. 从下至上计算d[i][j];

int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=i;j++)d[i][j]=a[i][j];
    }
    for(i=n-1;i>=1;i--){
        for(j=1;j<=i;j++)
            d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
    }

这招能通的秘诀在于：掌握了计算顺序。

### 方法3：记忆化 ###

伪代码兼思路

1. 给状态值都初始化为一个负数，这里不妨设为-1，memset(d,-1,sizeof(d));
    2. 调用**递归**状态转移函数计算状态值。如果状态值为正数，则得其本身，直接返回即可；状态值为负数，说明未计算过，就用递归的方法计算下。

实际上是在思路1的基础上，给每个结点一个状态标签，美其名曰**记忆化**。

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

转载于:https://www.cnblogs.com/MarkKobs-blog/p/10536210.html

[1084440-20190315122411826-721605733.png]: /images/20211223/6317b490711a43aca0419b4aa1881b88.png

动态规划篇一：初见动态规划

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关动态规划

相关动态规划

相关动态规划

相关动态规划入门篇

相关动态规划

相关动态规划

相关动态规划（一）

相关动态规划篇一：初见动态规划

相关动态规划

相关 DP动态规划专题（一）动态规划基本模型