动态规划——数塔（Java）（带完整代码及运行结果）

80 阅读 0 评论 53 点赞

我是靠谱客的博主英俊鲜花，最近开发中收集的这篇文章主要介绍动态规划——数塔（Java）（带完整代码及运行结果），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数塔的基本思路

代码部分（Java）

完整代码（带主函数）

运行结果

动态规划的基本思路已在上篇文章（多段图的最短路径）中提及，此篇不再做多余赘述。

数塔的基本思路：

•从数塔的顶层元素出发，在每个结点处去判断走左边还是走右边，一直走到底层，找到一条数值和最大的路径

代码部分（Java）：

int Datatower(int d[n][n])
{
	int maxAdd[n][n]={0},path[n][n]={0}; //初始化maxAdd和path
maxAdd记录每层的决策结果，是下三角矩阵；path记录路径
	int i,j;
	for(j=0;j<n;j++)  //将d数组中的最后一层元素赋值给maxAdd数组底层，即初始化maxAdd的底层元素
		maxAdd[n-1][j]= d[n-1][j];  
	for(i=n-2;i>=0;i--)	 //从第n-2层开始向上填入元素直到第0层
		for(j=0;j<=i;j++)  //找到即将要填写maxAdd[i][j]左边和右边中较大元素
			if(maxAdd[i+1][j]>maxAdd[i+1][j+1]) //左边的元素较大
			{
				maxAdd[i][j]=d[i][j]+maxAdd[i+1][j]; //maxAdd[i][j]记录为d[i][j]+左边元素(即较大者)
				path[i][j]=j; // 列号不变，选左边
			} 
            else //右边的元素较大
		    {															    	     
                maxAdd[i][j]=d[i][j]+maxAdd[i+1][j+1];
			    path[i][j]=j+1; //列号+1，选右边
		    } 
	printf("路径为:%d”,d[0][0]; //输出d数组的顶层元素是路径的起始
	j=path[0][0];  //顶层选择， 通过path[0][0]来判断其走向（若列下标不变，走左边；列下标+1，走右边。（这里的列下标指path[i][j]里的j））
	for(i=1;i<n;i++) 
	{//以此类推，找出每个的走向并输出路径
		printf("-->%d",d[i][j]);
		j=path[i][j];
	} 	
	return maxAdd[0][0];
}

完整代码（带主函数）：

static int [][] d ={{8},{12,15},{3,9,6},{8,10,5,12},{16,4,18,10,9}};
	public static int n=d.length;
	public static int maxAdd[][]=new int[n][n];
	public static int path[][]=new int[n][n];
	static int DataTower(){//数塔问题
		int i,j;
		for(j=0;j<n;j++)
			maxAdd[n-1][j]=d[n-1][j];
		for(i=n-2;i>=0;i--) {
			for(j=0;j<=i;j++) {
				if(maxAdd[i+1][j]>maxAdd[i+1][j+1]) {
					maxAdd[i][j]=d[i][j]+maxAdd[i+1][j];
					path[i][j]=j;
				}
				else {
					maxAdd[i][j]=d[i][j]+maxAdd[i+1][j+1];
					path[i][j]=j+1;
				}
			}
		}
		System.out.print("路径为："+d[0][0]);
		j=path[0][0];
		for(i=1;i<n;i++) {
			System.out.print("-->"+d[i][j]);
			j=path[i][j];
		}
	System.out.println();
	return maxAdd[0][0];	
	}

	public static void main(String[]args) {
		System.out.println("d数塔:");
		for(int i=0;i<d.length;i++) {
			for(int j=0;j<=i;j++) {
				System.out.printf("%-5d",d[i][j]);
			}
		System.out.println();
		}
		System.out.println("数组的最大数值为:"+DataTower());
		System.out.println();
		
		System.out.println("maxAdd:");
		for(int i=0;i<d.length;i++) {
			for(int j=0;j<=i;j++) {
				System.out.printf("%-5d",maxAdd[i][j]);
			}
		System.out.println();
		}
		
		System.out.println();		
		System.out.println("path:");
		for(int i=0;i<d.length;i++) {
			for(int j=0;j<=i;j++) {
				System.out.printf("%-5d",path[i][j]);
			}
		System.out.println();
		}	
	}