不用看我的，留个记录给自己印象

解题思路:
    看前面那位，写的非常好，写此题解完全为了做笔记

    分两种情况，第一种后面一个数为0，那就确定2位，长度加2，但是此时step要加1，"0_"

    第二种是不为0的情况，长度加1，step加1，‘_'

    最后找出step的数量，每个位置都有k-1种可能
注意事项:
    如果确定最后一位为0会出现多判段1位的情况，那就减去1个step

参考代码:

import java.io.*;

public class Main {
	static int sum;
	static int N;
	static int K;
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws NumberFormatException, IOException{
		N=Integer.parseInt(bf.readLine());
		K=Integer.parseInt(bf.readLine());
		dfs(1,1);
		pw.print(sum);
		pw.flush();
	}
	public static void dfs(int length,int step) {
		int[] next={1,2};
		int tlength,i;
		if(length==N) {
			sum+=Math.pow(K-1, step);
			return;
		}
		if(length==N+1) {
			sum+=Math.pow(K-1, step-1);
			return;
		}
		
		for(i=0;i<next.length;i++) {
			tlength=length+next[i];
			dfs(tlength,step+1);
		}
	}
}