剑指offer(C++)-JZ70:矩形覆盖(算法-动态规划)

简介: 剑指offer(C++)-JZ70:矩形覆盖(算法-动态规划)

题目描述:

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


数据范围:0≤n≤38

进阶:空间复杂度 O(1)  ,时间复杂度O(n)


注意:约定 n == 0 时,输出 0


比如n=3时,2*3的矩形块有3种不同的覆盖方法(从同一个方向看):

输入描述:

2*1的小矩形的总个数n

返回值描述:

覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)

示例:

输入:

4


返回值:

5

解题思路:

本题是类似青蛙跳台阶的题目,本质上是一个数学问题。


假设2*(n)矩形的覆盖方案数量是f(n),则2*(n)的大矩形有两种组合形式。2*(n-1)的大矩形加1块竖直的矩形是一种情况,2*(n-2)的大矩形加两块横放叠加的矩形是一种情况,所以f(n)=f(n-1)+f(n-2),显然是斐波那契数列了,用动态规划的解法即可。

测试代码:

class Solution {
public:
    int rectCover(int number) {
        // 当n为0、1、2时,可能的情况数量刚好和n一致
        if(number <= 2)
            return number;
        // 初始化
        int a = 1;
        int b = 2;
        int c = 0;
        // 斐波那契数列遍历
        for(int i = 3; i <= number; ++i)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

常规跳台阶问题可以参考:


剑指offer(C++)-JZ69:跳台阶(算法-动态规划)_翟天保Steven的博客-CSDN博客


该文章中提供了4种递优的解法,以帮助大家更好地理解动态规划。但该4种解法中最优解的时间复杂度也要O(n),因此我又探究了如何实现O(logn)的解法,将问题转换为矩阵求解的形式,运用快速幂的方法实现了高次幂的快速求解,达到了O(logn)水平。参考文章如下:


剑指offer(C++)-JZ10:斐波那契数列(时间复杂度O(logn)解法)_翟天保Steven的博客-CSDN博客


以上两篇文章都是解决斐波那契数列问题的相关内容,希望能对你有一些帮助。

相关文章
|
1月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
51 2
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
99 2
动态规划算法学习三:0-1背包问题
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
80 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
2月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
174 0
动态规划算法学习二:最长公共子序列
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
677 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
47 0
|
2月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
164 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
2月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)