剑指offer-10、矩阵覆盖
<h2 id="题目描述">题目描述</h2><p>我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2 * 1 的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？</p>
<p>比如n=3时，2 * 3 的矩形块有3种覆盖方法：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202507052049154.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<p>我们需要用若干个2×1的小矩形（可以横放或竖放）无重叠地覆盖一个2×n的大矩形，求总共有多少种不同的覆盖方法。例如当n=3时，共有3种覆盖方法。</p>
<p>通过观察小规模案例，我们可以发现：</p>
<ul>
<li>n=1时，只有1种方法（竖放）</li>
<li>n=2时，有2种方法（两个竖放或两个横放）</li>
<li>n=3时，有3种方法</li>
<li>n=4时，有5种方法</li>
</ul>
<p>显然，这形成了一个类似斐波那契数列的规律：f(n) = f(n-1) + f(n-2)。这一题其实和上面青蛙跳台阶和斐波那契数列是一样的，变的只是场景。</p>
<h3 id="递归">递归</h3>
<p>递归是解决这类问题最直观的方法。对于2×n的矩形，我们考虑第一块小矩形的放置方式：</p>
<ol>
<li>如果竖着放，则剩下的部分是2×(n-1)的矩形，有f(n-1)种方法</li>
<li>如果横着放，则下方也必须横放一块，剩下的部分是2×(n-2)的矩形，有f(n-2)种方法</li>
</ol>
<p>因此，总方法数为这两种情况之和：f(n) = f(n-1) + f(n-2)，这正是斐波那契数列的递推关系</p>
<pre><code class="language-java">public class Solution {
public int rectCover(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return rectCover(n - 1) + rectCover(n - 2);
}
}
</code></pre>
<ul>
<li>时间复杂度：O(2^n)，存在大量重复计算</li>
<li>空间复杂度：O(n)，递归调用栈深度</li>
</ul>
<h3 id="动态规划">动态规划</h3>
<p>在递归解法基础上，我们可以加入记忆化存储，避免重复计算。使用一个数组存储已经计算过的结果，每次计算前先检查是否已存储</p>
<pre><code class="language-java">public class Solution {
public int rectCover(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
int[] dp = new int;
for (int i = 2; i <= n; i++) {
dp = dp + dp;
}
return dp;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)，每个子问题只计算一次</li>
<li>空间复杂度：O(n)，需要存储中间结果</li>
</ul>
<h3 id="优化的动态规划空间优化">优化的动态规划（空间优化）</h3>
<p>观察发现，计算f(n)只需要前两个状态f(n-1)和f(n-2)，因此可以用两个变量代替整个数组，将空间复杂度优化到O(1)。</p>
<pre><code class="language-java">public class Solution {
public int rectCover(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
int prev1 = 1, prev2 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = prev2 + prev1;
prev1 = prev2;
prev2 = result;
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18967837
頁:
[1]