【算法优选】 动态规划之斐波那契数列模型

简介: 【算法优选】 动态规划之斐波那契数列模型


🎋前言

动态规划相关题目都可以参考以下五个步骤进行解答:

  1. 状态表⽰
  2. 状态转移⽅程
  3. 初始化
  4. 填表顺序
  5. 返回值

后面题的解答思路也将按照这五个步骤进行讲解。

🍀第 N 个泰波那契数

🚩题目描述

泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

  • 示例 1:
    输入:n = 4
    输出:4
    解释:
    T_3 = 0 + 1 + 1 = 2
    T_4 = 1 + 1 + 2 = 4
  • 示例 2:
    输入:n = 25
    输出:1389537
class Solution {
    public int tribonacci(int n) {
    }
}

🚩算法流程

  1. 状态表⽰:

这道题可以「根据题⽬的要求」直接定义出状态表⽰:

dp[i] 表⽰:第 i 个泰波那契数的值。

  1. 状态转移⽅程:

题⽬已经⾮常贴⼼的告诉我们了:

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

  1. 初始化:

从我们的递推公式可以看出, dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的,因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前,将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] = 0,dp[1] = dp[2] = 1 。

  1. 填表顺序:

毫⽆疑问是「从左往右」。

  1. 返回值:

应该返回 dp[n] 的值。

🚩代码实现

class Solution {
    public int tribonacci(int n) {
        int[] dp = new int[n + 3];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 0; i <  n; i++) {
            dp[i + 3] = dp[i] + dp[i + 1] + dp[i + 2];
        }
        return dp[n];
    }
}

🎄使用最小花费爬楼梯

🚩题目描述

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

  • 示例 1:
    输入:cost = [10,15,20]
    输出:15
    解释:你将从下标为 1 的台阶开始。
    -支付 15 ,向上爬两个台阶,到达楼梯顶部。
    总花费为 15 。
  • 示例 2:
    输入:cost = [1,100,1,1,1,100,1,1,100,1]
    输出:6
    解释:你将从下标为 0 的台阶开始。
    -支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
    -支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
    -支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
    -支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
    -支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
    -支付 1 ,向上爬一个台阶,到达楼梯顶部。
    总花费为 6 。
class Solution {
    public int minCostClimbingStairs(int[] cost) {
    }
}

🚩算法思路

🎈解法⼀:

  1. 状态表⽰:

这道题可以根据「经验+题⽬要求」直接定义出状态表⽰:

第⼀种:以 i 位置为结尾,然后一系列操作

dp[i] 表⽰:到达 i 位置时的最⼩花费。(注意:到达 i 位置的时候, i 位置的钱不需要算上)

  1. 状态转移⽅程:

根据最近的⼀步,分情况讨论:

▪ 先到达 i - 1 的位置,然后⽀付 cost[i - 1] ,接下来⾛⼀步⾛到 i 位置:dp[i - 1] + csot[i - 1] ;

▪ 先到达 i - 2 的位置,然后⽀付 cost[i - 2] ,接下来⾛⼀步⾛到 i 位置:dp[i - 2] + csot[i - 2] 。

  1. 初始化:

从我们的递推公式可以看出,我们需要先初始化 i = 0 ,以及 i = 1 位置的值。容易得到 dp[0] = dp[1] = 0 ,因为不需要任何花费,就可以直接站在第 0 层和第 1 层上。

  1. 填表顺序:

根据「状态转移⽅程」可得,遍历的顺序是「从左往右」。

  1. 返回值:

根据「状态表⽰以及题⽬要求」,需要返回 dp[n] 位置的值。

🎈解法⼆:

  1. 状态表⽰:

这道题可以根据「经验+题⽬要求」直接定义出状态表⽰:第⼆种:以 i 位置为起点,进行一系列操作。

dp[i] 表⽰:从 i 位置出发,到达楼顶,此时的最⼩花费。

  1. 状态转移⽅程:

根据最近的⼀步,分情况讨论:

▪ ⽀付 cost[i] ,往后⾛⼀步,接下来从 i + 1 的位置出发到终点: dp[i + 1] + cost[i] ;

▪ ⽀付 cost[i] ,往后⾛两步,接下来从 i + 2 的位置出发到终点: dp[i + 2] + cost[i] ;

我们要的是最⼩花费,因此 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i] 。

  1. 初始化:

为了保证填表的时候不越界,我们需要初始化最后两个位置的值,结合状态表⽰易得: dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]

  1. 填表顺序:

根据「状态转移⽅程」可得,遍历的顺序是「从右往左」。

  1. 返回值:

根据「状态表⽰以及题⽬要求」,需要返回 dp[n] 位置的值。也就是dp[0]与dp[1]中的较小值

🚩代码实现:

解法一:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        for(int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

解法二:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = cost.length;
        int[] dp = new int[n];
        dp[n - 1] = cost[n - 1]; dp[n - 2] = cost[n - 2];
        for(int i = n - 3; i >= 0; i--) {
            dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
        }
        return Math.min(dp[0], dp[1]);
    }
}

🌲解码方法

🚩题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> “1”

‘B’ -> “2”

‘Z’ -> “26”

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

“AAJF” ,将消息分组为 (1 1 10 6)

“KJF” ,将消息分组为 (11 10 6)

注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

  • 示例 1:
    输入:s = “12”
    输出:2
    解释:它可以解码为 “AB”(1 2)或者 “L”(12)。
  • 示例 2:
    输入:s = “226”
    输出:3
    解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
  • 示例 3:
    输入:s = “06”
    输出:0
    解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。
class Solution {
    public int numDecodings(String s) {
    }
}

🚩算法思路

类似于斐波那契数列~

  1. 状态表⽰:

根据以往的经验,对于⼤多数线性 dp ,我们经验上都是「以某个位置结束或者开始」做⽂章,这⾥我们继续尝试「⽤i位置为结尾」结合「题⽬要求」来定义状态表⽰。dp[i] 表⽰:字符串中 [0,i] 区间上,⼀共有多少种编码⽅法。

  1. 状态转移⽅程:

定义好状态表⽰,我们就可以分析 i 位置的 dp 值,如何由「前⾯」或者「后⾯」的信息推导出

来。

关于 i 位置的编码状况,我们可以分为下⾯两种情况:

  • 让 i 位置上的数单独解码成⼀个字⺟;
  • 让 i 位置上的数与 i - 1 位置上的数结合,解码成⼀个字⺟。

下⾯我们就上⾯的两种解码情况,继续分析:

  • 让i位置上的数单独解码成⼀个字⺟,就存在「解码成功」和「解码失败」两种情况:
  • 解码成功:当 i 位置上的数在 [1, 9] 之间的时候,说明 i 位置上的数是可以单独解码的,那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 1] 区间上的解码⽅法。因为 [0, i - 1] 区间上的所有解码结果,后⾯填上⼀个 i 位置解码后的字⺟就可以了。此时 dp[i] = dp[i - 1] ;
  • 解码失败:当 i 位置上的数是 0 的时候,说明 i 位置上的数是不能单独解码的,那么此时 [0, i] 区间上不存在解码⽅法。因为 i 位置如果单独参与解码,但是解码失败了,那么前⾯做的努⼒就全部⽩费了。此时 dp[i] = 0 。
  • 让 i 位置上的数与 i - 1 位置上的数结合在⼀起,解码成⼀个字⺟,也存在「解码成功」和「解码失败」两种情况:
  • 解码成功:当结合的数在 [10, 26] 之间的时候,说明 [i - 1, i] 两个位置是可以解码成功的,那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 2 ]区间上的解码⽅法,原因同上。此时dp[i] = dp[i - 2] ;
  • 解码失败:当结合的数在 [0, 9] 和 [27 , 99] 之间的时候,说明两个位置结合后解码失败(这⾥⼀定要注意 00 01 02 03 04 …这⼏种情况),那么此时 [0, i] 区间上的解码⽅法就不存在了,原因依旧同上。此时 dp[i] = 0 。

综上所述: dp[i] 最终的结果应该是上⾯四种情况下,解码成功的两种的累加和(因为我们关⼼的是解码⽅法,既然解码失败,就不⽤加⼊到最终结果中去),因此可以得到状态转移⽅程( dp[i] 默认初始化为 0 ):

  • 当 s[i] 上的数在 [1, 9] 区间上时: dp[i] += dp[i - 1] ;
  • 当 s[i - 1] 与 s[i] 上的数结合后,在 [10, 26] 之间的时候: dp[i] += dp[i - 2] ;

如果上述两个判断都不成⽴,说明没有解码⽅法, dp[i] 就是默认值 0 。

  1. 初始化:
  • ⽅法⼀(直接初始化):
    由于可能要⽤到 i - 1 以及 i - 2 位置上的 dp 值,因此要先初始化「前两个位置」。
    初始化 dp[0] :
  • 当 s[0] == ‘0’ 时,没有编码⽅法,结果 dp[0] = 0 ;
  • 当 s[0] != ‘0’ 时,能编码成功, dp[0] = 1

初始化 dp[1] :

  • 当 s[1] 在 [1,9] 之间时,能单独编码,此时 dp[1] += dp[0] (原因同上,dp[1] 默认为 0 )
  • 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时,说明在前两个字符中,⼜有⼀种编码⽅式,此时 dp[1] += 1
  • ⽅法⼆(添加辅助位置初始化):
    可以在最前⾯加上⼀个辅助结点,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要保证后续填表是正确的;
  • 下标的映射关系
  1. 填表顺序:

毫⽆疑问是「从左往右」

  1. 返回值:

应该返回 dp[n - 1] 的值,表⽰在 [0, n - 1] 区间上的编码⽅法。

🚩代码实现

class Solution {
    public int numDecodings(String ss) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n];
        if(s[0] != '0') {
            dp[0] = 1; // 初始化第⼀个位置
        }
        if(n == 1) {
            return dp[0]; // 处理边界情况
        }
        // 初始化第⼆个位置
        if(s[1] != '0' && s[0] != '0') {
            dp[1] += 1;
        }
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if(t >= 10 && t <= 26) {
            dp[1] += 1;
        }
        for(int i = 2; i < n; i++) {
            // 先处理第⼀种情况
            if(s[i] != '0') {
                dp[i] += dp[i - 1];
            }
            // 处理第⼆种情况
            int tt = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n - 1];
    }
}

代码优化如下:

class Solution {
    public int numDecodings(String ss) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1; // 保证后续填表是正确的
        if(s[1 - 1] != '0') dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            // 先处理第⼀种情况
            if(s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            // 处理第⼆种情况
            int tt = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2]; 
            }
        }
        return dp[n];
    }
}

⭕总结

关于《【算法优选】 动态规划之斐波那契数列模型》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

相关文章
|
25天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
55 2
动态规划算法学习三:0-1背包问题
|
6天前
|
机器学习/深度学习 人工智能 算法
青否数字人声音克隆算法升级,16个超真实直播声音模型免费送!
青否数字人的声音克隆算法全面升级,能够完美克隆真人的音调、语速、情感和呼吸。提供16种超真实的直播声音模型,支持3大AI直播类型和6大核心AIGC技术,60秒快速开播,助力商家轻松赚钱。AI讲品、互动和售卖功能强大,支持多平台直播,确保每场直播话术不重复,智能互动和真实感十足。新手小白也能轻松上手,有效规避违规风险。
|
7天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
11天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
32 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
27天前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
19 4
|
25天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
58 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
25天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
100 0
动态规划算法学习二:最长公共子序列
|
25天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
89 0
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。