当前位置:网站首页>圆环回原点问题-字节跳动高频题
圆环回原点问题-字节跳动高频题
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
圆环上有10个点,编号为0~9。从0点出发,每次可以逆时针和顺时针走一步,问走n步回到0点共有多少种走法。
示例 1:
输入: 2
输出: 2
解释:有2种方案。分别是0->1->0和0->9->0
二、解题
动态规划
这题类似于爬楼梯,使用动态规划:走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
dp[i][j]表示从0点出发走i步到j点的方案数。
状态转移方程:
- 走i步走到j的有n中方法 等于 {走i-1步到 j-1} + {走 i-1步到j+1},因为有回环,所以需要走到j-1可能为负数
- dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1+length)%length];
class Solution {
public int backToOrigin(int k) {
int[][] dp = new int[k + 1][10];
dp[0][0] = 1;
for (int i = 1; i <= k ; i++) {
for (int j = 0; j < 10; j++) {
dp[i][j] = dp[i - 1][(j - 1 + 10) % 10] + dp[i - 1][(j + 1) % 10];
}
}
return dp[k][0];
}
}
延伸
class Solution {
public int backToOrigin(int n, int k) {
if (n == 0) {
return 1;
}
if (n == 2) {
if (k % 2 == 0) {
return k;
} else {
return 0;
}
}
int[][] dp = new int[k + 1][n];
dp[0][0] = 1;
for (int i = 1; i < k + 1; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][(j - 1 + n) % n] + dp[i - 1][(j + 1) % n];
}
}
return dp[k][0];
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124332502
边栏推荐
- 开期货,开户云安全还是相信期货公司的软件?
- If you start from zero according to the frame
- Using quartz under. Net core - [1] quick start
- JS to find the character that appears three times in the string
- EF core in ASP Generate core priority database based on net entity model
- [C#] 彻底搞明白深拷贝
- MySQL installation
- JS failed to change all variables and changed to the return method. Finally, the problem was solved
- 開期貨,開戶雲安全還是相信期貨公司的軟件?
- Use of five routing guards
猜你喜欢
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
If you start from zero according to the frame
For the space occupation of the software, please refer to the installation directory
Learning record of uni app dark horse yougou project (Part 2)
Understanding of RPC core concepts
Future 用法详解
.Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
Scope and scope chain in JS
Net standard
随机推荐
超分之TDAN
Simulation of infrared wireless communication based on 51 single chip microcomputer
Scope and scope chain in JS
Solution of Navicat connecting Oracle library is not loaded
Advantages and disadvantages of several note taking software
Generation of barcode and QR code
tidb-server 的配置文件在哪里?
Promise (III)
1-2 characteristics of nodejs
STM32 entry development board choose wildfire or punctual atom?
Detailed explanation of C webpai route
ASP. NET CORE3. 1. Solution to login failure after identity registers users
[二叉数] 二叉树的最大深度+N叉树的最大深度
古代埃及希腊,数学用的什么进制
Using quartz under. Net core -- a simple trigger of [7] operation and trigger
QT modification UI does not take effect
El cascade and El select click elsewhere to make the drop-down box disappear
El date picker limits the selection range from the current time to two months ago
Low code development platform sorting
Input file upload