18年阿里测评题

发表于 | 分类于 | 阅读次数

感觉算法题可以分为两类

  • 一类是使用既定的规则去解题，按照规则解就好了，无非就是超时嘛，那就需要想怎么优化了
  • 一类是无法解决的题目，就是一眼看到后不知道怎么做，那么这样的题目都可以用大问题转小问题解决，就是我们知道它的最小问题怎么解决，那我们就像给定的n问题转化为n-1的问题，最后到1的问题，这就是递归问题中的DFS或者BFS。这样也会有超时的情况，因为有很多个子问题是重复的，那我们用数组记录下已有的子问题就可以了，这就是DP了。

将一个圆形等分成N个小扇形，将这些扇形标记为1，2，3,…，N。现在使用M种颜色对每个扇形进行涂色，每个扇形涂一种颜色，且相邻的扇形颜色不同
问有多少种涂法？

涂扇形问题

看到这道题，我是不知道怎么做的，那就找规律，但是也找不出来，那就将问题缩小，那么有n个小扇形怎么变成有n-1个小扇形呢，或者说n-1个小扇形怎么变成n个小扇形呢？
可以把n个小扇形的涂法问题转为在n-1个已经涂好的小扇形中添加一个小扇形，此时有一个问题，n-1个小扇形的涂法中是不允许两两之间有重复颜色的，但是对于添加位置，左右两边是可以使用重复颜色的，因为被中间的隔开了，也就是说我们转换成了两个子问题

  1. 第一个子问题就是常规的n-1个小扇形的涂法，然后我在这些位置中添加一个小扇形，这个小扇形的颜色只要不同于添加位置的左右两边的颜色就可以了，有m-2种方法。
  2. 第二个子问题就是n-1个小扇形中，出现了两个相邻的位置颜色相同，那么可以把这两个相邻位置的小扇形看成一个小扇形，也就是n-2个小扇形的涂法，然后我们在它们之间添加一个小扇形，只要不是该颜色就可以了，有m-1种方法。

于是得到通向公式

然后找初始条件

好了，就可以写个递归的形式了，当然也可以使用二维矩阵构建DP解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ALCP01 {
    public static int getNumF(int n,int m){
        int r;
        if (n == 1) r = m;
        else if (n == 2) r = m * (m - 1);
        else if (n == 3) r = m * (m - 1)*(m - 2);
        else {
            r = getNumF(n - 1, m)*(m - 2) + getNumF(n - 2, m)*(m - 1);
        }
        return r;
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n,m;
        n=scanner.nextInt();
        m=scanner.nextInt();
        scanner.close();
        System.out.println(getNumF(n,m));
    }
}

如果觉得有帮助，给我打赏吧！