Dp解决三角形最短路径问题

动态规划解决三角形最短路径问题

三角形最小路径和 (下一个数的选择范围只能在与自己相邻的下一级的两个数之间)
2
3 4
6 5 7
4 1 8 3
例： 2+3+5+1 =11

import java.util.Arrays;


public class DpToggleMinPath {
	/*
	 * 动态规划解决这个问题
	 * 4 1 8 3按照规则加上上一行的相邻的数
	 * 规划到上一行
	 * f(6)=4+6=10;
	 * f(6)=1+6=7;
	 * f(5)=1+5=6;
	 * f(5)=8+5=13;
	 * f(7)=8+7=15;
	 * f(7)=3+7=10
	 * 继续上一行
	 * f(3)=f(6)+3=13或10
	 * f(3)=f(5)+3=9或16
	 * f(4)=f(5)+4=10或17
	 * f(4)=f(7)+4=19或14
	 * 到第一行
	 * f(2)=f(3)+2=15或12或11或18
	 * f(2)=f(4)+2=12或19或21或16
	 */
	private static int minPath=2;
	private static int j=0;//计数器,用来给数组扩容
	private static int p=0;//计数器,用来区分每次规划
	private static int[][] minPathArray=new int[1][1];
	public static void main(String[] args) {
		int [][] path={{2},{3,4},{6,5,7},{4,1,3,8}};//三角形
		for(int i=path.length-1;i>1;i--){
			//在最后一层中取最小值,我给每层都取了最小值不过不影响会覆盖掉
			minPath=getPart(path,i)+2;//最终结果
		}
		    /*
		     * 二维数组里的每个一维数组为一层的规划结果
		     * minPathArray[minPathArray.length-1][q]+2 是因为一层只有一个元素最后给规划结果加上就好
		     * q<minPathArray[minPathArray.length-1].length-1
		     * 获取第一层的规划结果最后的减一是因为最后扩容时多了一次其值为0
		     */
			for(int q=0;q<minPathArray[minPathArray.length-1].length-1;q++){
			 System.out.println(q+1+"路径="+(minPathArray[minPathArray.length-1][q]+2));
			}
		
		System.out.println(minPath);
	}
	/*
	 * 动态规划
	 * 得到局部最优解
	 * 然后合并解得到最优解
	 */
	public static int getPart(int[][] path,int x){
		int count=0,count1=0,totalcount=0;
		j=0;//每次进来,重置j
		p++;//每进来一次,行扩充一次
		minPathArray=Arrays.copyOf(minPathArray,minPathArray.length+1);//扩容
		minPathArray[p]=new int[1];
		for(int i=0;i<path[x].length;i++){
		//如果是最后一行
		if(x==path.length-1){
		if(i==0){
			minPathArray[p][j]=path[x][i]+path[x-1][i];//如果是第一个元素则加上层第一个元素
		}else if(i==path[x].length-1){
			minPathArray[p][j]=path[x][i]+path[x-1][i-1];//如果是最后一个元素则加上上层最后一个元素
		}else{
			//否则中间元素为加上肩膀上两个
			minPathArray[p][j]=path[x][i]+path[x-1][i-1];//左边元素
			minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);//扩容
			j++;//上一个已赋值下标加一
			minPathArray[p][j]=path[x][i]+path[x-1][i];//右边元素
		}
		//给前两种情况准备因为它们赋值后没操作
		   j++;
		   minPathArray[p]=Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
			}else if(x!=1&&totalcount<path[x].length-1){//如果不是第一层并且遍历次数小于该层长度
				totalcount++;
				/*
				 * 该循环是根据规律进行的
				 * 当p=2即对2层第1层进行规划时
				 *   . //第二层也为8个 同第一层                                这层每个元素的路径数量为:2^2(p)=4(不理解看开头的推导)
				 *........ //第三层规划结果 此时p=2,结果有8个  这层每个元素的路径数量为:2^1(p)=2
				 * ......//这个为最后一层规划的结果有6个此时p=1;p=0为一个初始数组 private static int[][] minPathArray=new int[1][1]
				 * 跟据以上内容我们发现有个规律
				 *   1.上一层每个元素可以规划的路径数量=Math.pow(2,p)
				 *   2.我们每次循环实际上是对上层的每个元素求它的路径数
				 *   3.i==0是即第一个元素我们把该层的第一个元素的所有路径数与上层的相加
				 *   4.i==path[x].length-1与上同理只不过是与上层最后一个元素
				 *   5.else 最后把中间的元素的路径数与上层相邻的两个元素的路径求和
				 *   @param index 这个变量用来计算路径下标
				 *   @param count,count1由于循环次数不确定而我们第二个元素与倒数第二个元素之求两次(因为第一个和最后一个元素已经求了相邻两个)
				 *
				 *
				 */
				for(int m=0;m<Math.pow(2,p);m++){
				int index=(int)(i*Math.pow(2,p-1))+m;
				if(i==0){
					minPathArray[p][j]=minPathArray[p-1][m]+path[x-1][i];
					minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
					j++;
				}else if(i==path[x].length-1){
					minPathArray[p][j]=minPathArray[p-1][minPathArray[p-1].length-m-1]+path[x-1][i-1];
					minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
					j++;
				}else{
					if(i==1&&count1<2){
						minPathArray[p][j]=minPathArray[p-1][index]+path[x-1][i];
						minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
						j++;
						count1++;
						}	
				else if(i==path[x].length-2&&count<2){
						minPathArray[p][j]=minPathArray[p-1][index]+path[x-1][i];
						minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
					    j++;
						count++;
					    }
						else{
							minPathArray[p][j]=minPathArray[p-1][index]+path[x-1][i-1];
							minPathArray[p]= Arrays.copyOf(minPathArray[p],minPathArray[p].length+1);
							j++;
							minPathArray[p][j]=minPathArray[p-1][index]+path[x-1][i];
							
						}
					}
				}
			}
			}
		return  findMin();
	}
	//寻找最小值
	public static int findMin(){
		int min=minPathArray[p][0];
		for(int i=1;i<minPathArray[p].length;i++){
			if(minPathArray[p][i]<min&&minPathArray[p][i]!=0){
				min=minPathArray[p][i];
			}
		}
		return min;
	}
};