阿里笔试7.29解法
2.n 个客栈依次排列，给出 n - 1 条路的权重。从任意一处出发，每走过一条路，该路的权重减 1，但得到 1 点利益。不能走权重为 0 的路。求最大利益。
解法代码
import java.util.*;
public class Main{
public static void main(String[] args) {
List<Integer> line = new LinkedList(Arrays.asList(5,2,4));
Map<String,Integer> dp = new HashMap<>();
Integer maxValue = -1;
for(int i = 0;i < line.size() + 1;++i){
List<Integer> lineTmp = new LinkedList<>(line);
String key = toStringKey(lineTmp,i);
dp.put(key,0);
}
while(!dp.isEmpty()){
Map<String,Integer> preDp = dp;
dp = new HashMap<>();
for(Map.Entry<String,Integer> entry : preDp.entrySet()){
String key = entry.getKey();
List<Integer> tmpLine = getLineFromKey(key);
Integer tmpIndex = getNodeIndexFromKey(key);
Integer tmpVal = entry.getValue();
if(tmpIndex == tmpLine.size()){
Integer lineSize = tmpLine.get(tmpIndex - 1);
if(lineSize > 0){
tmpLine.set(tmpIndex - 1,lineSize - 1);
tmpVal += 1;
tmpIndex -= 1;
String tmpKey = toStringKey(tmpLine,tmpIndex);
if(dp.containsKey(tmpKey)){
dp.put(tmpKey,Math.max(dp.get(tmpKey),tmpVal));
maxValue = Math.max(tmpVal,maxValue);
}else{
dp.put(tmpKey,tmpVal);
maxValue = Math.max(tmpVal,maxValue);
}
}
}else if(tmpIndex == 0){
Integer lineSize = tmpLine.get(tmpIndex);
if(lineSize > 0){
tmpLine.set(tmpIndex,lineSize - 1);
tmpVal += 1;
tmpIndex += 1;
String tmpKey = toStringKey(tmpLine,tmpIndex);
if(dp.containsKey(tmpKey)){
dp.put(tmpKey,Math.max(dp.get(tmpKey),tmpVal));
maxValue = Math.max(tmpVal,maxValue);
}else{
dp.put(tmpKey,tmpVal);
maxValue = Math.max(tmpVal,maxValue);
}
}
}else{
Integer lineSize1 = tmpLine.get(tmpIndex);
Integer lineSize2 = tmpLine.get(tmpIndex - 1);
if(lineSize1 > 0){
tmpLine.set(tmpIndex,lineSize1 - 1);
tmpVal += 1;
tmpIndex += 1;
String tmpKey = toStringKey(tmpLine,tmpIndex);
if(dp.containsKey(tmpKey)){
dp.put(tmpKey,Math.max(dp.get(tmpKey),tmpVal));
maxValue = Math.max(tmpVal,maxValue);
}else{
dp.put(tmpKey,tmpVal);
maxValue = Math.max(tmpVal,maxValue);
}
tmpIndex -= 1;
tmpVal -= 1;
tmpLine.set(tmpIndex,lineSize1);
}
if(lineSize2 > 0){
tmpLine.set(tmpIndex - 1,lineSize2 - 1);
tmpVal += 1;
tmpIndex -= 1;
String tmpKey = toStringKey(tmpLine,tmpIndex);
if(dp.containsKey(tmpKey)){
dp.put(tmpKey,Math.max(dp.get(tmpKey),tmpVal));
maxValue = Math.max(tmpVal,maxValue);
}else{
dp.put(tmpKey,tmpVal);
maxValue = Math.max(tmpVal,maxValue);
}
}
}
}
}
System.out.println(maxValue);
}
public static String toStringKey(List<Integer> line,Integer index){
StringBuilder sb = new StringBuilder();
for(Integer i : line){
sb.append(i).append(":");
}
sb.append(index);
return sb.toString();
}
public static List<Integer> getLineFromKey(String key){
String[] lineAndIndex = key.split(":");
List<Integer> data = new LinkedList<>();
for(int i = 0;i < lineAndIndex.length - 1;++i){
data.add(Integer.parseInt(lineAndIndex[i]));
}
return data;
}
public static Integer getNodeIndexFromKey(String key){
String[] lineAndIndex = key.split(":");
return Integer.parseInt(lineAndIndex[lineAndIndex.length - 1]);
}
}