从一道阿里的笔试题了解动态规划
动物之王
选动物老大，n个小动物，编号1-n,代表武力值，值越小，武力值越高，每个小动物都有一票投票权，可以投给自己或者自己崇拜的动物，或者和自己崇拜的动物跟票。
只能崇拜武力值比自己厉害的动物。
输入：第一行：n个动物 4
后面n行:
第几个小动物的崇拜对象 0 1 1 1
输出：每个小动物的最多的投票 4 1 1 1
解释：当第一个动物投自己 其余动物都投自己的崇拜的1号 那一号最多可以拿四票 然后其他动物如果都投自己 那么其余动物最多可以拿一票
这道题更多的考察的是一个动态规划的问题
每一个小动物都有三种选择
-
一种是选择投票给自己 -
一种是投票给自己崇拜的人 -
一种是和自己崇拜的人一样投相同的票
我们可以先构建一个数组来说明一下这三种情况发生的时候的场景
构建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]+" ");
}
}
}