阿里笔试题 广告牌问题

题目描述：

有三种广告牌，A、B和C，其中A占一块，B占两块，C占三块；并且A不能与A相邻，B、C没有限制。

输入广告区域总长度n，求有几种放置广告牌的方案。

思路：

做笔试的时候想成了动态规划问题，一直找不到规律，现在看来应该用回溯法。（反正我依然不知道动态规划该怎么做）

困扰了很久！脑壳疼！

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static List<List<Integer>> combinationSum( int target){
        int[] cans={1,2,3};
        List<List<Integer>> result = new ArrayList<>();
        int[] length = new int[target];
        backtrack(result,length,cans,target,0);
        System.out.println(result.size());
        return result;
    }

    /**
     * @param result 存放结果的list
     * @param nums 当前遍历的结果
     * @param cans 代表三种广告牌的长度
     * @param remain 放置广告牌后的剩余长度
     * @param numcount 当前为放置的第几块
     */
    public static void backtrack(List<List<Integer>> result,int[] nums,int[] cans,int remain,int numcount){
        if(remain == 0){
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < numcount; i++) {
                list.add(nums[i]);
            }
            result.add(list);
        }else if(remain < 0){
        }else {
            for (int i = 0; i < 3; i++) {
                if(i!=0||numcount==0||nums[numcount-1]!=cans[0]){
                    nums[numcount] =cans[i];
                    backtrack(result,nums,cans,remain-cans[i],numcount+1);
                }
            }
        }
    }

    public static void main(String[] args) {
        combinationSum(1);
        combinationSum(2);
        combinationSum(3);
        combinationSum(4);
        combinationSum(5);
        combinationSum(6);
        combinationSum(7);
        combinationSum(8);

    }
}