java深度优先搜索

解题思路:将k进制看作[0~k)个数，填入N个坑位中，可以重复，转换为深度优先搜索思想；

注意事项:当遇到第一个0时候，设置标记lastZero = true;连续遇到0时，选择跳过，而且第一个坑位不能是0
参考代码:

import java.util.Scanner;

public class Main
{
   static int count = 0;//计数
   static int[] nums;//存[0~k)个数

   static int[] res;//将N位数结果记录
   static int N,K;
   static boolean lastZero = false;//标记遇到的第一个0
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
       nums = new int[K];
       res = new int[N];
       int step = 0;
       for (int i = 0;i<K;i++) {
           nums[i] = i;
       }
       dfs(nums,step);
       System.out.println(count);


   }

   private static void dfs(int[] nums, int step) {
   if (step == N )//当递归至已经存入N位数时
   {
           count++;
       return;
   }
   for (int i = 0;i<K;i++)
   {
       if ((lastZero && i == 0) || step == 0 && i==0)//遇到连续两个0或者第一个存入数遇到0
       {
           lastZero = false;//回溯
           continue;
       }
       if (i == 0)//遇到第一个0
           lastZero = true;    
       else//没遇到0
           lastZero = false;
        res[step] = nums[i];
        dfs(nums,step+1);
   }

   }
}