从一道阿里的笔试题了解动态规划

动物之王   

    选动物老大，n个小动物，编号1-n,代表武力值，值越小，武力值越高，每个小动物都有一票投票权，可以投给自己或者自己崇拜的动物，或者和自己崇拜的动物跟票。

   只能崇拜武力值比自己厉害的动物。

输入：第一行：n个动物     4

后面n行:

第几个小动物的崇拜对象    0 1 1 1

输出：每个小动物的最多的投票    4 1 1 1

解释：当第一个动物投自己 其余动物都投自己的崇拜的1号 那一号最多可以拿四票  然后其他动物如果都投自己 那么其余动物最多可以拿一票

这道题更多的考察的是一个动态规划的问题

每一个小动物都有三种选择

1. 一种是选择投票给自己
2. 一种是投票给自己崇拜的人
3. 一种是和自己崇拜的人一样投相同的票

我们可以先构建一个数组来说明一下这三种情况发生的时候的场景

构建h数组 索引1-n代表着1号动物到n号动物所得到最大票数

构建arr数组 索引1-n 代表着1号动物到n号动物所崇拜的人是谁

0 代表着谁都不崇拜

当前动物的编号是n 崇拜的人是n-3

而n-3编号的动物崇拜的人是n-6

1.投票给自己 h[n]++

2.投票给崇拜的人 h[arr[n]]++ (此时arr[n]=n-3)

3.和自己崇拜的人投一样的票

 h[h[arr[n]]]++(此时arr[n]=n-3 h[arr[n]]=h[n-3]=n-6)

我们针对所有的可能性 罗列了数组以及其赋值情况

当然遍历的顺序也是很重要的

题目中有一句话是这样的

每个动物只能崇拜武力值比自己厉害的动物

所以假设当前编号为n 那么只能崇拜 0 或者1-（n-1)的动物了

所以遍历顺序为从前往后遍历就行了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Ali1 {
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String line[]=r.readLine().split(" ");
        int n=Integer.valueOf(line[0]);//总共有几个动物
        String line1[]=r.readLine().split(" ");
        int[] arr=new int[n+1];
        for (int i = 1; i <=n ; i++) {
            arr[i]=Integer.valueOf(line1[i-1]);
        }        //索引变成了1-n 代表每个动物崇拜的人
        int[] f=new int[n+1];//开辟一个数组存放投票的最大值
        f[1]=1;//从1号开始 一号只能选0 所以先赋值为1
        for (int i = 2; i <=n ; i++) {//从2号开始遍历
            f[i]+=1;//第一种情况 是0
            if(arr[i]==0){
                continue;
            }
            else{
                for (int j = arr[i]; j !=0 ; j=arr[j]) {
                    f[j]+=1;//第二或者第三种情况 投给崇拜的人 或者跟着崇拜的人跟票
                }
            }
        }

        for (int i = 1; i <=n ; i++) {
            System.out.print(f[i]+" ");
        }
    }
}