当前位置:网站首页>[leetcode sword finger offer 10 - II. Frog jumping steps (simple)]
[leetcode sword finger offer 10 - II. Frog jumping steps (simple)]
2022-04-23 21:21:00 【Minaldo7】
subject :
A frog can jump up at a time 1 Stepped steps , You can jump on it 2 Stepped steps . Ask the frog to jump on one n How many jumps are there in the steps .
The answer needs to be modelled 1e9+7(1000000007), If the initial result of calculation is :1000000008, Please return 1.
Example 1:
Input :n = 2
Output :2
Example 2:
Input :n = 7
Output :21
Example 3:
Input :n = 0
Output :1
Tips :
0 <= n <= 100
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
The problem solving process :
class Solution {
public int numWays(int n) {
// if(n == 0 || n == 1) return 1;
// int front = 1, back = 1, fibn =0;
// for(int i = 2;i<=n;i++){
// fibn = front + back;
// if(fibn >= 1000000007)
// fibn -= 1000000007;
// front = back;
// back = fibn;
// }
// return fibn;
if(n <= 1) return 1;
int dp[] = new int[n+1];
dp[0] = 1;
dp[1] = 1;
//dp[2] = 2;
for(int i = 2; i < n+1; i++){
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
return dp[n];
}
}
Execution results :
notes : Multiplication of large numbers , Why should we take modules for the permutation and combination of large numbers ?
because :1000000007 It's a prime number ( prime number ), The remainder of prime numbers can avoid the conflict of results to the greatest extent / repeat
版权声明
本文为[Minaldo7]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/111/202204210544479549.html
边栏推荐
- Write table of MySQL Foundation (create table)
- GSI-ECM工程建设管理数字化平台
- Rust更适合经验较少的程序员?
- Explore ASP Net core read request The correct way of body
- opencv应用——以图拼图
- Getting started with detectron2
- MySQL basic collection
- Pikachuxss how to get cookie shooting range, always fail to return to the home page
- IOT 设计与开发
- DeNO 1.13.2 release
猜你喜欢
2. Finishing huazi Mianjing -- 2
On the three paradigms of database design
3-5 obtaining cookies through XSS and the use of XSS background management system
MySQL进阶之数据的增删改查(DML)
Pipes and xargs
Deep analysis of C language pointer (Part I)
wait、waitpid
Chrome 94 introduces the controversial idle detection API, which apple and Mozilla oppose
go interface
浅谈数据库设计之三大范式
随机推荐
C#,打印漂亮的贝尔三角形(Bell Triangle)的源程序
Addition, deletion, modification and query of advanced MySQL data (DML)
Problem brushing plan -- dynamic programming (III)
Graph traversal - BFS, DFS
Google tries to use rust in Chrome
Thread safe sigleton (singleton mode)
Detectron2 usage model
Flomo software recommendation
MySQL进阶之表的增删改查
flomo软件推荐
Two Stage Detection
Norm normalization in tensorflow and pytorch of records
1. Finishing huazi Mianjing -- 1
Addition, deletion, modification and query of MySQL advanced table
Question brushing plan -- backtracking method (I)
Pytorch preserves different forms of pre training models
2.整理华子面经--2
The computer is out of power. How did I pass the terrible interview of Tencent cloud?
Fastdfs思维导图
Fastdfs mind map