算法沉淀 —— 动态规划篇(斐波那契数列模型)

简介: 算法沉淀 —— 动态规划篇(斐波那契数列模型)

算法沉淀 —— 动态规划篇(斐波那契数列模型)

前言

几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此


  • 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。
  • 以i为结尾,dp[i] 表示什么,通常为代求问题(具体依题目而定)
  • 以i为开始,dp[i]表示什么,通常为代求问题(具体依题目而定)
  • 2、状态转移方程
    *以上述的dp[i]意义为更具, 通过最近一步来分析和划分问题,由此来得到一个有关dp[i]的状态转移方程。
  • 3、dp表创建,初始化
  • 动态规划问题中,如果直接使用状态转移方程通常会伴随着越界访问等风险,所以一般需要初始化。而初始化最重要的两个注意事项便是:保证后续结果正确,不受初始值影响;下标的映射关系
  • 初始化一般分为以下两种:
  • 直接初始化开头的几个值。
  • 一维空间大小+1,下标从1开始;二维增加一行/一列
  • 4、填dp表、填表顺序:根据状态转移方程来确定填表顺序。
  • 5、确定返回值

一、第 N 个泰波那契数

【题目链接】:1137. 第 N 个泰波那契数

【题目】:

【分析】:

 题目要第n个斐波那契数,我们令dp[i]表示第i个斐波那契数。题目中以及给出了状态转移方程:dp[i] = dp[i-1] + dp[i-2] +dp[i-3]。但我们发现当i为0、1、2时显然状态转移方程错误,还会越界访问。所以我们仅需将前3个元素特殊处理,然后在从下标2开始填dp表。最后返回结果即可!

【代码实现】:

class Solution {
public:
    int tribonacci(int n) {
        if(n == 0)
            return 0;
        else if(n == 1 || n == 2)
            return 1;
        //创建dp表
        vector<int> dp(n + 1);
        //初始化
        dp[0] = 0, dp[1] = dp[2] = 1;
        //填表
        for(int i = 3; i <= n; i++) 
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};

二、三步问题

【题目链接】:面试题 08.01. 三步问题

【题目】:

 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

【分析】:

 我们可以定义dp[i]表示小孩走到i阶台阶时上楼方式的最大值。由题目可知,小孩一次可以走1阶、2阶、3阶。所以我们容易得到状态转移方程为dp[i] = dp[i-1] + dp[i-2] + dp[i-3](题目明确表示结果肯过大,记得模1000000007!!)。

 显然你以及观察到当i <=3时,状态转移方程不适应。所以我们可以提前将前3个dp表中的值进行初始化;然后在从左往右依次填表。最后返回结果即可!!

【代码实现】:

class Solution {
public:
    int waysToStep(int n) {
        //特殊处理
        if(n == 1)
            return 1;
        else if(n == 2)
            return 2;
        else if(n == 3)
            return 4;
        const int DEL = 1000000007;
        vector<int> dp(n + 1);//创建dp表,多开一个空间,让下标对应
        //初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
        //填表
        for(int i = 4; i <= n; i++)
            dp[i] = (dp[i - 1] + (dp[i - 2] + dp[i - 3]) % DEL) % DEL;
        return dp[n];
    }
};

三、使用最小花费爬楼梯

【题目链接】:746. 使用最小花费爬楼梯

【题目】:

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

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

实例:

【分析】

 我们可以用dp[i]变化到达下标为i的台阶时的最低花费。题目中指出,一步可选择向上爬一个或者两个台阶。所以dp[i]必然是从i-1阶或i-2阶台阶爬上来的,易得状态转移方程为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

 显然当i为0、1时需要单独处理(处理为0)。但C++vector创建dp表时,已经将所有数据初始化为0,所以此步不需要单独实现。然后就是从下标2开始,从左往右依次填dp表了。最后返回结果即可!!

【代码实现】:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //创建dp表
        int n = cost.size();
        vector<int> dp(n + 1);
        //填表
        for(int i = 2; i <= n; i++)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[n];
    }
};

四、解码方法

【题目链接】:91. 解码方法

【题目】:

一条包含字母 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位的整数。

【分析】:

 我们定义dp[i]表示从下标[0, i]的子字符串的解法方式总数。显然解码到dp[i]的最近一步分为:从[0,i-1] 加s[i],如果s[i]合法,此时d[i] += dp[i-1];从[0, i-2] 加s[i-1,i],如果s[i-1, i]合法,此时dp[i] += dp[i-2]。所以我们可以得到对应的状态转移方程。(具体看代码)

 显然我们需要将dp[1]、dp[2]单独处理,就不多说了。然后从左往右依次填表,最后返回结果!!

【代码实现】:

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        //创建dp表
        vector<int> dp(n);
        //初始化
        dp[0] = s[0] != '0';
        if(n == 1)
            return dp[0];
        if(s[0] != '0' && s[1] != '0')
            dp[1]++;
        int tmp = (s[0] - '0') * 10 + s[1] - '0';
        if(tmp >= 10 && tmp <= 26)
            dp[1]++;
        //填表
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0')
                dp[i] += dp[i - 1];
            int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(tmp >= 10 && tmp <= 26)
                dp[i] += dp[i - 2] ;
        }
        return dp[n - 1];
    }
};

相关文章
|
4天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
19 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
4天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
22 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
9天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
26 2
|
1月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
65 2
动态规划算法学习三:0-1背包问题
|
15天前
|
机器学习/深度学习 人工智能 算法
青否数字人声音克隆算法升级,16个超真实直播声音模型免费送!
青否数字人的声音克隆算法全面升级,能够完美克隆真人的音调、语速、情感和呼吸。提供16种超真实的直播声音模型,支持3大AI直播类型和6大核心AIGC技术,60秒快速开播,助力商家轻松赚钱。AI讲品、互动和售卖功能强大,支持多平台直播,确保每场直播话术不重复,智能互动和真实感十足。新手小白也能轻松上手,有效规避违规风险。
|
17天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
20天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
65 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
1月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
65 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
118 0
动态规划算法学习二:最长公共子序列
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
100 0