/** * 作者：爱做梦的病人 * 链接：https://www.nowcoder.com/discuss/582954?channel=666&source_id=feed_index_nctrack * 起源：牛客网 * * 一个环上有0,1,2,3,4,5，6,7,8,9 共计10个节点，一个指针起始地位在0节点，每次只能走一步，能够顺时针走也能够逆时针走，请问走了n步之后再回到0节点，请问总共有多少种不同的形式？ * 例如n=1,门路有（0,1），（0,9），输入0 * n=2,门路有（0,1,2）（0,1,0）（0,9,0）（0,9,8） 输入2 * @param n * @return */这道题首先最简略的办法就是递归了。
int res = 0;public int fun(int n){ dfs(0,n); return res;}/** * * @param i:以后索引 * @param n：还剩几步 */private void dfs(int i, int n) { //走完了 if (n == 0){ //是否回到了0点 if (i == 0){ //总办法数加一 res++; } return; } //顺时针 int nextL = (i + 1) % 10; dfs(nextL,n-1); //逆时针 int nextR = (i - 1) % 10; dfs(nextR,n-1);}然而很显著其实还能够优化，就是用动静布局。
咱们用一个二维数组matrix来记录办法数。
martrixi示意在还剩i步时，以后地位是j,有martrixi种办法达到0点。
咱们从1步开始算，算到n步，最初matrixn的意思就是以后地位是0，还剩n步，有matrixn种办法走到0点，所以matrixn就是咱们要的答案。
public int dp(int n){ //matrix[i][j]示意在还有i步时，以后地位为j，能够有matrix[i][j]种办法走到0点 int[][] matrix = new int[n+1][10]; //只剩0步时，只能有0种办法（这里其实能够不写，写进去是不便了解） for (int i = 0;i < 10;i++) { matrix[0][i] = 0; } //初始化，只剩一步时，1,9地位都有一种办法达到0点，其它地位都是0种办法 matrix[1][1] = 1; matrix[1][9] = 1; //i示意剩几步，从2步开始算 for (int i =2;i < n+1;i++) { //j示意以后地位 for (int j = 0;j < 10;j++) { if(j>0&&j<9) //达到0点办法数等于前一步的两个地位之和（j-1和j+1代表顺/逆序时针的前一步地位） matrix[i][j] = matrix[i - 1][j + 1] + matrix[i - 1][j - 1]; if(j==0) //这里也是计算前一步的两个地位之和，但地位减一会小于0，所以间接用9代替逆时针的前一步地位 matrix[i][j] = matrix[i - 1][j + 1] + matrix[i - 1][9]; if (j == 9) matrix[i][j] = matrix[i - 1][0] + matrix[i - 1][j-1]; } } return matrix[n][0];}