当前位置:网站首页>圆环回原点问题-字节跳动高频题
圆环回原点问题-字节跳动高频题
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
边栏推荐
- Router object, route object, declarative navigation, programmed navigation
- Signalr can actively send data from the server to the client
- 给 el-dialog 增加拖拽功能
- Promise (IV)
- Using quartz under. Net core - calendar of [6] jobs and triggers
- Come out after a thousand calls
- Clickhouse table engine
- 1-5 nodejs commonjs specification
- Self use learning notes - connected and non connected access to database
- If you start from zero according to the frame
猜你喜欢
Allowed latency and side output
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
ASP. Net core dependency injection service life cycle
Use of five routing guards
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
1-4 configuration executable script of nodejs installation
1217_使用SCons生成目标文件
[WPF binding 3] listview basic binding and data template binding
JVM类加载机制
For the space occupation of the software, please refer to the installation directory
随机推荐
ClickHouse-数据类型
El cascade and El select click elsewhere to make the drop-down box disappear
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
[difference between Oracle and MySQL]
1-5 nodejs commonjs specification
ASP. Net core configuration options (Part 1)
1-1 NodeJS
Ouvrir des contrats à terme, ouvrir des comptes en nuage ou faire confiance aux logiciels des sociétés à terme?
Exercise: even sum, threshold segmentation and difference (two basic questions of list object)
Clickhouse table engine
Header built-in object
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
In embedded system, must the program code in flash be moved to ram to run?
RPC核心概念理解
超分之TDAN
Shell-awk命令的使用
JS failed to change all variables and changed to the return method. Finally, the problem was solved
[batch change MySQL table and corresponding codes of fields in the table]
Use of shell cut command
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory