poj1163 递归或dp

红太狼 2022-06-13 10:51 137阅读 0赞

递归的版本：很可惜tle了。

package p1163;
    
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
    
    public class Main {
    	static int count = 105;
    	static int d[][] = new int[count][count];
    	static int n;
    
    	public static void main(String[] args) throws FileNotFoundException {
    		//File f = new File("c:\\data.txt");
    		//Scanner cin = new Scanner(f);
    		 Scanner cin = new Scanner(System.in);
    		n = cin.nextInt();
    		for (int i = 1; i <= n; i++) {
    			for (int j = 1; j <= i; j++) {
    				d[i][j] = cin.nextInt();
    			}
    		}
    		System.out.println(func(1, 1));
    	}
    
    	// i行，j列，j<=i
    	static int func(int i, int j) {
    		int max = 0;
    		if (i < n) {
    			max = d[i][j] + max(func(i + 1, j), func(i + 1, j + 1));// 往下，往右
    		} else {
    			max = d[i][j];
    		}
    		return max;
    	}
    
    	static int max(int a, int b) {
    		return a > b ? a : b;
    	}
    }

想了一下，tle的原因主要是递归是从上往下计算的。那么用动规呢，从下往上计算。

\--------------------------------------------------------------------------粉葛\--------------------------------------------------------------------------

动规的版本：

import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
    
    public class Main {
    	static int count = 105;
    	static int d[][] = new int[count][count];
    	static int res[][] = new int[count][count];//使用res存储已经计算出来的数据
    	static int n;
    
    	public static void main(String[] args) throws FileNotFoundException {
    		//File f = new File("c:\\data.txt");
    		//Scanner cin = new Scanner(f);
    		 Scanner cin = new Scanner(System.in);
    		n = cin.nextInt();
    		for (int i = 1; i <= n; i++) {
    			for (int j = 1; j <= i; j++) {
    				d[i][j] = cin.nextInt();
    			}
    		}
    
    		for (int i = 1; i <= n; i++) {
    			res[n][i] = d[n][i];
    		}
    		// 从下往上动规
    		for (int i = n; i >= 1; i--) {
    			for (int j = 0; j <= i; j++) {
    				res[i][j] = d[i][j] + max(res[i + 1][j], res[i + 1][j + 1]);
    			}
    		}
    		System.out.println(res[1][1]);//最后，res数组的顶层的那个元素就是要求的最大值
    	}
    
    	static int max(int a, int b) {
    		return a > b ? a : b;
    	}
    }

其实动规跟上面的递归版本，差不是很多。都是从底层计算，然后向上层累加。只是递归版本的应该是需要递归很多次，所以算上递归返回的时间，就tle了吧。