动态规划—数塔问题

思路：用一个二维数组（三角阵）存储数塔，用另一个数组存储每次决策后的值，最后数组的第一个元素就是最优的。
从下往上，依次找最优的那一个。
d[i][j]=data[i][j]+max(d[i+1][j],d[i+1][j+1])

package shuta;

import java.util.Scanner;

public class number01 {
	public static void main(String args[]) {
		Scanner input=new Scanner(System.in);
		System.out.println("请输入数塔的规模，层数= ");
		int n=input.nextInt();
		int data[][]=new int[n][n];
		int d[][]=new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<i+1;j++) {
				data[i][j]=input.nextInt();
				d[i][j]=data[i][j];
			}
		}
		for(int i=n-2;i>=0;i--) {
			for(int j=0;j<=n-2;j++) {
				d[i][j]=data[i][j]+max(d[i+1][j],d[i+1][j+1]);
				}
			}
		
		System.out.println("最优解为 fine= "+d[0][0]);
	}
	static int max(int i,int j) {
		if(i>j)return i;
		else return j;
	}
}

最后

以上就是神勇大门为你收集整理的动态规划—数塔问题的全部内容，希望文章能够帮你解决动态规划—数塔问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。