算法基础--递归和动态规划

栏目: 编程工具 · 发布时间: 5年前

内容简介:从非依赖关系入手。明确的知晓n!=1×2×3×...×n,然后按照顺序编写算法即可从依赖关系入手。n已知,尝试解决(n-1)!打印N层汉诺塔从最左边移动到最右边的全部过程
算法基础--递归和动态规划

本文主要作为自己的学习笔记,并不具备过多的指导意义。

暴力递归

  1. 把问题转化为规模缩小了的同类问题的子问题

  2. 有明确的不需要继续递归的条件

    base case

求n!的结果

非递归版本

从非依赖关系入手。明确的知晓n!=1×2×3×...×n,然后按照顺序编写算法即可

func getFactorial1(n : Int) -> Int {
    var res = 1
    for i in 1..<n+1 {
        res = res * i
    }
    
    return res
}
复制代码

递归版本

从依赖关系入手。n已知,尝试解决(n-1)!

func getFactorial2(n : Int) -> Int {
    if n == 1 {
        return 1
    }
    return n * getFactorial2(n: n-1)
}
复制代码

汉诺塔问题

打印N层汉诺塔从最左边移动到最右边的全部过程

每次一个,不能打压小只能小压大

算法基础--递归和动态规划

在第N层的问题上,需要完成以下三个状态:

第N层的完成依赖N-1的完成,而第N-1层的完成又依赖N-1层的完成。

算法基础--递归和动态规划
/// 移动1-N层汉诺塔
///
/// - Parameters:
///   - n: 需要移动到的层数
///   - form: 从哪根开始
///   - to: 从哪根结束
///   - help: 空那根
func hanoiGame(n : Int ,form :String ,to :String ,help :String) {
    if n == 1 {//只移动第一层,直接移动即可
        print("Move 1 from " + form + " to " + to)
    }else {
        hanoiGame(n: n-1, form: form, to: help, help: to)  //将第 1到n-1 层移动到 中间
        print("Move \(n) " + "from " + form + " to " + to) //将第 n 层移动到 最右
        hanoiGame(n: n-1, form: help, to: to, help: form) //将第 1到n-1 层移动到 最右
    }
}



hanoiGame(n: 3, form: "左", to: "右", help: "中")
//打印
Move 1 from 左 to 右
Move 2 from 左 to 中
Move 1 from 右 to 中
Move 3 from 左 to 右
Move 1 from 中 to 左
Move 2 from 中 to 右
Move 1 from 左 to 右
复制代码

打印字符串能组成的所有字串

输入abc 打印:abc,ab,ac,a,bc,b,c

将字符串转化成数组,每个位置都有两个选择:打印&&跳过。以此递归

代码

func printStr(str :String) {
    printAllSub(str: wordToArr(word: str), i: 0, res: "")
}

func printAllSub(str :[String] ,i :Int ,res :String) {
    if i == str.count {
        print(res)
    }else {
        printAllSub(str: str, i: i+1, res: res+str[i]) //打印当前位置
        printAllSub(str: str, i: i+1, res: res) //不打印当前位置
    }

}

func wordToArr(word:String) -> Array<String> {
    var res : [String]
    res = Array.init()
    if word.count == 0 {
        return res
    }
    let string = (word as NSString)
    for i in 0..<string.length {
        res.append(string.substring(with: NSMakeRange(i, 1)))
    }
    
    return res
}

复制代码

母牛数目问题

有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?

当思维不够直观的时候,不妨列举一下试试查找规律

算法基础--递归和动态规划

F(N) = F(N-1) + F(N-3)

第五年 = 第四年存活的 + A与第二年出生的B所生的两个

需要注意:如果N-3为负数则不用计算,只计算母牛自己生的一个即可

func func(n : Int) -> Int {
    if n == 1 {
        return 1
    }
    if n - 3 <= 0 {
        return func1(n: n-1) + 1
    }else {
        return func1(n: n-1) + func1(n: n-3)
    }
}
复制代码

二维数组--从左上角到右下角最大值

只能向右或向下走

经典的动态规划题目,但我们可以先从递归做起

/// 二维数组--从左上角到右下角最大值
///
/// - Parameters:
///   - matrix: 二维矩阵
///   - x: x轴坐标
///   - y: y轴坐标
/// - Returns: 当前点到右下角最小距离
func walk(matrix : [[Int]] ,x :Int ,y :Int) -> Int {
    if (x == matrix.count-1) && (y == matrix[0].count-1) { //已经到最后
        return matrix[x][y] //返回当前节点
    }
    
    if x == matrix.count-1 {  //已经到x轴末尾
        return matrix[x][y] + walk(matrix: matrix, x: x, y: y+1) //当前节点+y轴下一位
    }
    
    if y == matrix[0].count-1 { //已经到y轴末尾
        return matrix[x][y] + walk(matrix: matrix, x: x+1, y: y) //当前节点+x轴下一位
    }
    
    //当前节点+min(x轴下一位,y轴下一位)
    return matrix[x][y] + min(walk(matrix: matrix, x: x+1, y: y), walk(matrix: matrix, x: x, y: y+1))
}

复制代码

暴力递归的弊端

第一次进入 walk(0,0) 时,将会递归调用蓝色位置 walk(1,0)walk(0,1)

算法基础--递归和动态规划

而在进入 walk(1,0) 时,又将递归调用 walk(2,0)walk(1,1) 并且进入 walk(0,1) 时,又将递归调用 walk(0,2)walk(1,1)

算法基础--递归和动态规划

此时 walk(1,1) 将会执行两次,其之后的递归计算也指数级的重复。

这就是动态规划的意义,解决暴力递归重复执行的缺点进行优化

动态规划

所有的动态规划,都是从暴力递归尝试优化(减少重复计算)而来

面试中,对于一个没有见过的动态规划。我们可以先写出一个递归的尝试版本,在验证正确性之后尝试改成动态规划。

递归方法的后效性

如上文中所提到的 暴力递归的弊端 一样:有些暴力递归会存在重复状态,并且这些重复状态的结果与到达其的路径无关( 状态的参数确定,返回值则确定 )。

什么样的问题可以改成动态规划

对于 无后效性递归 ,可以改成动态规划的版本。

也有反例:比如汉诺塔问题,每一步打印都会对整体的打印结果造成影响。就叫有后效性递归,无法进行动态规划。

无后效性递归如何改成动态规划的通用方法

二维数组--从左上角到右下角最大值 题目为例:

  1. 分析可变参数,建立状态表

    以每个状态的return结果建立一个二维数组。

  2. 找到自己需要的最终状态位置(0,0)

    算法基础--递归和动态规划
  3. 回到base case 中,对不被依赖的位置进行设置

    算法基础--递归和动态规划
  4. 对普遍位置进行设置

    算法基础--递归和动态规划
  5. 最终得到目标位置

数组中元素是否能组成指定的和

先写一个正常的暴力递归尝试版本,与之前 打印字符串能组成的所有字串 的问题基本一致

/// 数组中元素是否能组成指定的和
///
/// - Parameters:
///   - arr: 数组
///   - i: 当前位置
///   - sum: 已经求的和
///   - aim: 目标和
/// - Returns: 结果
func isSum(arr :[Int] ,i :Int ,sum :Int ,aim :Int) -> Bool {
    if i == arr.count { //数组末尾已经尝试结束
        return aim==sum //直接比对
    }
    
    let useC = isSum(arr: arr, i: i+1, sum: sum+arr[i], aim: aim) //尝试添加当前位置
    
    let unuseC = isSum(arr: arr, i: i+1, sum: sum, aim: aim) //不添加当前位置
    
    return useC || unuseC
}
复制代码

如何转变成动态规划

  1. 简化表达式,并建立动态规划表

    只有两个可变参数,可以简化成 F(i,sum)

    DP表的设计行为sum(最后一位为所有元素之和),列为i。 在代码上,将作为一个二维数组存在

    算法基础--递归和动态规划
  2. 确定目标位置

    算法基础--递归和动态规划
  3. base case中找到不被依赖的位置 只有在F(N,Aim)时, aim==sum 才会返回 true

    算法基础--递归和动态规划
  4. 对普遍位置进行设置 某一个位置 F(i,sum1) 的状态依赖于 F(i+1,sum1)F(i+1,sum1)+arr[i]F(i+1,sum1)+arr[i] 又作为新的sum值 Sum2 存在于DP表内。 两个位置有一个为Aim,则将返回true

    算法基础--递归和动态规划
  5. 推回到最初位置


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

信息简史

信息简史

[美] 詹姆斯·格雷克 / 高博 / 人民邮电出版社 / 2013-10 / 69.00元

人类与信息遭遇的历史由来已久。詹姆斯•格雷克笔下的这段历史出人意料地从非洲的鼓语讲起(第1章)。非洲土著部落在尚未直接跨越到移动电话之前,曾用鼓声来传递讯息,但他们是如何做到的呢?后续章节进而讲述了这段历史上几个影响深远的关键事件,包括文字的发明(第2章)、罗伯特•考德里的第一本英语词典(第3章)、查尔斯•巴贝奇的差分机与爱达•拜伦的程序(第4章)、沙普兄弟的信号塔与摩尔斯电码(第5章)。 ......一起来看看 《信息简史》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具