阿里笔试7.29解法

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]);
    }
    
}