题目:小猴子下山,沿着下山的路有一排桃树,每棵树都结了一些桃子。小猴子想摘桃子,但是有一些条件需要遵守,小猴子只能沿着下 山的方向走,不能回头,每颗树最多摘一个,而且一旦摘了一棵树的桃子,就不能再摘比这棵树结的桃子少的树上的桃子。那么小 猴子最多能摘到几颗桃子呢?举例说明,比如有5棵树,分别结了

  1. 云栖社区>
  2. 博客>
  3. 正文

题目:小猴子下山,沿着下山的路有一排桃树,每棵树都结了一些桃子。小猴子想摘桃子,但是有一些条件需要遵守,小猴子只能沿着下 山的方向走,不能回头,每颗树最多摘一个,而且一旦摘了一棵树的桃子,就不能再摘比这棵树结的桃子少的树上的桃子。那么小 猴子最多能摘到几颗桃子呢?举例说明,比如有5棵树,分别结了

anmypeng1 2018-03-17 20:44:27 浏览1071
展开阅读全文

package com.hp.algorithm.mostpeach;

import java.util.ArrayList;
import java.util.List;
public class MostPeach
{

public static int currMaxPeachNum = 0;//当前摘的最大一颗树
public static int mostPeach(List<Integer> treeWithPeach){
    if(null == treeWithPeach){
        return 0;
    }
    if(1 == treeWithPeach.size()){
        if(currMaxPeachNum > treeWithPeach.get(0)){
            return 0;
        }
        return 1;
    }

    int pick = 0;
    int notPick = 0;
    if(currMaxPeachNum <= treeWithPeach.get(0)){
        //情况1:当前桃子树大于currMaxPeachNum,摘。摘了之后还要摘后面的树
        currMaxPeachNum = treeWithPeach.get(0);
        pick = 1 + mostPeach(treeWithPeach.subList(1, treeWithPeach.size()));
    }

    //情况2:当前桃子树大于currMaxPeachNum,不摘
    //情况3:当前桃子树小于currMaxPeachNum,不摘
    notPick = mostPeach(treeWithPeach.subList(1, treeWithPeach.size()));

    if(pick > notPick){
        return pick;
    }
    return notPick;
}
/**
 * @param args
 */
public static void main(String[] args)
{
    List<Integer> case1 = new ArrayList<Integer>();
    case1.add(5);case1.add(10);case1.add(4);case1.add(5);case1.add(12);case1.add(8);
    List<Integer> case2 = new ArrayList<Integer>();
    case2.add(5);case2.add(3);case2.add(5);case2.add(4);
    List<Integer> case3 = new ArrayList<Integer>();
    case3.add(1);
    System.out.println(mostPeach(case3));
}

}

网友评论

登录后评论
0/500
评论
anmypeng1
+ 关注