牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.-笔试面试资料

这是qklbishe.com第6607 篇笔试面试资料
提供答案分析,通过本文《牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.

牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出. 区块链毕设学生306634497号
很典型的动态规划问题,但我属于看出来这个的题型但是不知道该咋做的菜鸡。。。参考了百度出来的c++解法才理解的。设共有f(n)种情况,如果我们先横着放一块1*2的地毯时剩下的情况是f(n-1),如果我们先竖着放一块1*2的地毯时剩下的情况是f(n-2),如果先放上一块2*3的地毯时剩下的情况是是f(n-3)。即f(n) = f(n-1)+ f(n-2)+ f(n-3)。也就等同于青蛙跳台阶有三种跳法,跳1阶、跳2阶、跳3阶的情况。
这里写递归的话会超时,因此直接用dp来做:

import java.util.Scanner; public class Main{     public static void main(String[] args){         //已知最大值为100000,则初始化一个长度为100001的数组         int[] dp = new int[100001];         dp[1] = 1;         dp[2] = 2;         dp[3] = 4;         //计算出所有情况,记得模上10007         for(int i = 4; i < 100001; i++){             dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3])%10007;         }         //获取输入的值         Scanner scanner = new Scanner(System.in);         while(scanner.hasNext()){             int nums = scanner.nextInt();             for(int i = 0; i < nums; i++){                 System.out.println(dp[scanner.nextInt()]);             }         }     } }

2021-02-12 22:05:58 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.-笔试面试资料

提供最优质的资源集合

立即查看 了解详情