递归与动态规划----基础篇2

ps:最近几天正在刷一些有关动态规划的题,我会把自己学习时的想法以及做题的想法记录下来。如果你觉得对你有帮助,欢迎关注,谢谢。

如果你没看过基础篇1,可以看一看勒

递归与动态规划---基础篇1

下面为大家讲解另外两道,难度会提升一点点

数字三角形案例

题目描述 Description

下图给出了一个数字三角形,请编写一个程序,
计算从顶至底的某处的一条路径,
使该路径所经过的数字的总和最大。 
注意:每一步可沿左斜线向下或右斜线向下 
输入描述:
第1行是输入整数
(如果该整数是0,就表示结束,不需要再处理),
表示三角形行数n,然后是n行数
样例输入: 
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

解题思路: 对于这种有多种选择的题,一般都可以使用递归的方法来做,上节讲过,对于递归的题,最重要的 就是找出递归的两个条件:

1. 两个函数之间存在的关系
2. 递归结束的临界条件

我们先来声明一些变量来记录一些东西

    1. 用D(i,j)这个二维数组来记录这个数字三角形,
i表示第i行,j表示第j列,D(i,j)表示第i行j列这个点的值
    2. MaxSum(i, j) : 从D(r,j)到底边的各条路径中,
最佳路径的数字之和(动态规划记录状态会用到)
    3. state(i,j):用来记录D(i,j)这个点是否计算过,
如果还没有计算过,则state(i,j) = -2,
否则state(i,j) = MaxSum(i,j).

现在我们来寻找递归的两个条件

1. 我们从第0行开始一直走,显然,当我们走到最后一行时,递归结束,此时i = n-1(因为我们从第0行开始算)

2. 当我们处在D(i, j)这个点时,我们可以笔直往下走,也可以斜着往下走,有两种走法 。我们的目标时找出使总路径较大的点,可以得到递归公式:

MaxSum(i,j) = max{MaxSum(i+1, j), MaxSum(i+1, j+1)} + D(i, j)

找出了这两个条件,就好做了。代码如下:

int MaxSum(int i, int j){
if(i == n-1)
    return D[i][j];//最底层,把该点的路径值返回
int x = MaxSum(i + 1, j);//计算笔直向下走时的最优路径
int y = MaxSum(i + 1, j + 1);//计算斜向下走时的最优路径
return max(x,y) + D[i][j];
}

问题所在:

和上次讲的一样,这种递归属于暴力递归,会有很多重复计算的。和上次讲的跳台阶那个类似。时间复杂度是O(2的n次方)

重复计算的次数如下图所示

下面我们采用动态规划的方法(递归动态保存)

    其实,我们可以每次在计算D(i,j)的时候,
把计算出来的最优解MasSum(i,j)保存起来,
下次需要的时候,先查看D(i,j)是否之前计算过,
如果计算过,直接取出来就可以了。
前面说过我们把值存放在state(i,j)这个数组里。

代码如下所示

`   int MaxSum(int i, int j){
if(i == num)//临界值
    return D[i][j];
else if (state[i][j] != -2)//表示这个 点已经计算过了
{
    return state[i][j]//直接取出返回
}else//否则的话就只好乖乖计算
{
    int x = MaxSum(i + 1, j);
    int y = MaxSum(i + 1, j + 1);
    state[i][j] = max(x,y) + D[i][j];//保存起来
    return state[i][j];
}
}`

时间复杂度为O(n2)O(n2),因为三角形的数字总和为n(n+1)/2n(n+1)/2

ps:其实这道题也可以用递推方法的动态递归来接,
从底部往上算起,有兴趣的可以思考下。
有兴趣且想不出的可以问我勒

二、

学这个最重要的就是多练些题了,刚开始的时候尽量找写简单点的题,函数与函数之间的递归关系比较容易 找的题。下面找给大家介绍道题,和上次讲的类型比较一样,算是比较基础的题:

问题:
    我们可以用2*1的小矩形横着或者竖着去
覆盖更大的矩形。请问用n个2*1的小矩形无重
叠地覆盖一个2*n的大矩形,总共有多少种方法?

还是我说的一样,找出

(1).递归的结束条件。

(2).函数与函数之间的递归关系

1.先找结束条件:

(1)当 n < 1时,显然不需要用2*1块覆盖,应该返回 0。

(2)当 n = 1时,只存在一种情况

(3)当 n = 2时,存在两种情况

(4)当 n > 2时,显然是需要横着放和竖着,这时两种情况交替放,就会产生递归的之间的函数关系(下图是n=3的情况)

即 f(n) = f(n-1) + f(n-2). (有木发现这些题都很类似,解法几乎一样)

代码如下所示

int f(int n){
    if(n < 1)return 0
    else if(n == 1)return 1
    else if(n == 2)return 2
    else return f(n-1) + f(n-2)
}

老规矩,这样做,有很多重复算的,采用动态记录的方法。以n为key,f(n)为value保存在map容器中

     Map<Integer , Integer> m = new HashMap<>();
    int f5(int n){
        if(n < 1){
            return 0;
        }
        else if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            if(m.containsKey(n)){
                return m.get(n);
            }else{
                int sum = f5(n-1) + f5(n-2);
                map.put(n, sum);
                return sum;
            }
        }
    }

如果你有其他想法,或者更完美的做法,欢迎指点江山。

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

LOJ #108. 多项式乘法

内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

37480
来自专栏mathor

搜索(6)

 题目大意是在一个nxn的方阵地图上,每一个方格都标记+号或者-号,要从A点到B点。题目要求移动路线要+-交替,问怎么移动从A到B才是最短路径?  同样...

15030
来自专栏网络和编程

float类型加法精度损失问题(C++)

奇怪的就是:a依然是406682816,并没有加一。网上查了一些资料,这里分享一下原因。

513150
来自专栏ACM算法日常

POJ1258:Agri-Net-最小生成树

Farmer John has been elected mayor of his town! One of his campaign promises was...

10820
来自专栏王肖的UT

GLSL-内置函数

74730
来自专栏Python小屋

详解Python列表推导式

列表推导式可以使用非常简洁的方式对列表或其他可迭代对象的元素进行遍历和过滤,快速生成满足特定需求的列表,代码具有非常强的可读性,是Python程序开发时应用最多...

51240
来自专栏進无尽的文章

数据结构与算法 - 时间复杂度与空间复杂度

时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费...

89320
来自专栏不止思考

算法的时间与空间复杂度(一看就懂)

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有...

12020
来自专栏技术总结

算法(2)

25090
来自专栏专知

Numpy教程第1部分 - 阵列简介(常用基础操作总结)

【导读】这里是numpy教程的基础部分,涵盖了使用numpy的ndarrays执行数据操作和分析的一些操作。众所周知,Numpy是Python中最基本和最强大的...

29540

扫码关注云+社区

领取腾讯云代金券