從一道阿里的筆試題了解動態(tài)規(guī)劃

動物之王? ?

? ? 選動物老大，n個小動物，編號1-n,代表武力值，值越小，武力值越高，每個小動物都有一票投票權(quán)，可以投給自己或者自己崇拜的動物，或者和自己崇拜的動物跟票。

? ?只能崇拜武力值比自己厲害的動物。

輸入：第一行：n個動物? ? ?4

后面n行:

第幾個小動物的崇拜對象? ? 0 1 1 1

輸出：每個小動物的最多的投票? ? 4 1 1 1

解釋：當(dāng)?shù)谝粋€動物投自己 其余動物都投自己的崇拜的1號 那一號最多可以拿四票? 然后其他動物如果都投自己 那么其余動物最多可以拿一票

思路

這道題更多的考察的是一個動態(tài)規(guī)劃的問題

每一個小動物都有三種選擇

1. 一種是選擇投票給自己
2. 一種是投票給自己崇拜的人
3. 一種是和自己崇拜的人一樣投相同的票

我們可以先構(gòu)建一個數(shù)組來說明一下這三種情況發(fā)生的時候的場景

構(gòu)建h數(shù)組?索引1-n代表著1號動物到n號動物所得到最大票數(shù)

構(gòu)建arr數(shù)組?索引1-n 代表著1號動物到n號動物所崇拜的人是誰

0 代表著誰都不崇拜

舉例

當(dāng)前動物的編號是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)

要注意的地方

我們針對所有的可能性 羅列了數(shù)組以及其賦值情況

當(dāng)然遍歷的順序也是很重要的

題目中有一句話是這樣的

每個動物只能崇拜武力值比自己厲害的動物

所以假設(shè)當(dāng)前編號為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];//開辟一個數(shù)組存放投票的最大值
????????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]+"?");
????????}
????}
}

---END---
程序IT圈-技術(shù)交流群已成立
掃碼可添加小猿助手，可申請加入IT圈交流群，一定要備注：開發(fā)方向+地點+學(xué)校/公司+昵稱，根據(jù)格式備注，可更快被通過且邀請進(jìn)群

▲長按加群
更多技術(shù)好文，推薦關(guān)注