120. Triangle

 1 class Solution {
 2     int min(int []n)
 3     {
 4         if(n.length<1)return 0;
 5         int r=n[0];
 6         for(int i=1;i<n.length;++i)
 7         {
 8             r=Math.min(r,n[i]);
 9         }
10         return r;
11     }
12     public int minimumTotal(List<List<Integer>> triangle) {
13         if(triangle.size()<1)return 0;
14         int []last=new int[1]; 
15         last[0]=triangle.get(0).get(0).intValue(); //第一行不用算就是第一个元素
16         for(int row=1;row<triangle.size();++row)//从第二行开始
17         {
18             List<Integer> line=triangle.get(row);
19             int []cur=new int[line.size()];
20             cur[0]=last[0]+line.get(0).intValue(); //首尾值比较特殊只能是上一行的最左/右值加上这行的最左/右值
21             cur[line.size()-1]=last[line.size()-2]+line.get(line.size()-1).intValue();
22             
23             for(int i=1;i<line.size()-1;++i)//循环本行的中间部分, 去掉最左和最右
24             {
25                 cur[i]=line.get(i).intValue()+Math.min(last[i-1],last[i]); //本行第i个数可以和上一行的i-1或者i进行相加,所以取min的情况
26             }
27             last=cur;
28         }
29         return min(last);//不知道java 有没有库函数可以直接算数组最小值的...只能自己写一个
30     }
31 }

三角形查找和最小/大的路径.

要么暴力运算,要么就是用dp.

这题的话dp其实和暴力运算差不多的,其实就是用数组来储存上一行的结果,和上楼梯的题目类似.