首页 > 其他 > 详细

leetcode Triangle

时间:2014-05-24 05:54:01      阅读:389      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣

分析:从最小面一层开始往上计算,设dp[i][j]是以第i层j个元素为起点的最小路径和,动态规划方程如下


dp[i][j] = value[i][j] + max{dp[i-1][j], dp[i-1][j+1]}


因为每一层之和它下一层的值有关,因此只需要一个一位数组保存下层的值,



public
int minmumTotalDP(ArrayList<ArrayList<Integer>> triangle){ int rows=triangle.size(); int[] dp=new int[rows]; //初始化值、、动态规划 for(int i=0;i<rows;i++){ dp[i]=triangle.get(rows-1).get(i); } for(int i=rows-2;i>=0;i--){ for(int j=0;j<=i;j++) dp[j]=Math.min(dp[j], dp[j+1])+triangle.get(i).get(j); } return dp[0]; }
bubuko.com,布布扣
bubuko.com,布布扣
 private int minValue ;
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        }
        minValue= Integer.MAX_VALUE;
        int n = triangle.size();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        getResult(triangle, stack, 1, n, triangle.get(0).get(0));
        return minValue;
    }
    private void getResult(ArrayList<ArrayList<Integer>> triangle,
            Stack<Integer> stack, int index, int n, int sum) {
        // TODO Auto-generated method stub
        if (index == n) {
            if (sum < minValue) {
                minValue = sum;
            }
            stack.pop();
            return;
        }
        int left = stack.peek();
        stack.push(left);
        getResult(triangle, stack, index + 1, n,
                sum + triangle.get(index).get(left));
        int right = stack.peek() + 1;
        stack.push(right);
        getResult(triangle, stack, index + 1, n,
                sum + triangle.get(index).get(right));
        stack.pop();
    }
bubuko.com,布布扣

 

leetcode Triangle,布布扣,bubuko.com

leetcode Triangle

原文:http://www.cnblogs.com/csxf/p/3736505.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!