动态规划题目

面试题10- I. 斐波那契数列

	//递归法：超时！！！
	public int fib(int n) {
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		return fib(n-1)+fib(n-2);
	}
	
	public int fib1(int n) {
		/**
		 * 由于 dp列表第 i 项只与第 i−1 和第 i−2项有关，
		 * 因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum
		 *  使 a,b 两数字交替前进即可 （具体实现见代码） 。
		 * */
		int a=0,b=1,sum;
		for (int i = 0; i < n; i++) {
			sum=(a+b)%1000000007;
			a=b;
			b=sum;
		}
		return a;
	}

剑指 Offer 10- II. 青蛙跳台阶问题

	public int numWays(int n) {
		int a = 1, b = 1, sum;
		for (int i = 0; i < n; i++) {
			sum = (a + b) % 1000000007;
			a = b;
			b = sum;
		}
		return a;
	}

剑指 Offer 42. 连续子数组的最大和

	public int maxSubArray(int[] nums) {
		int res = nums[0];
		for (int i = 1; i < nums.length; i++) {
			nums[i] += Math.max(nums[i - 1], 0);
			res = Math.max(res, nums[i]);
		}
		return res;
	}

剑指 Offer 47. 礼物的最大价值

public int maxValue(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		int[][] dp = new int[m + 1][n + 1];

		for (int i = 0; i < m + 1; i++) {
			for (int j = 0; j < n + 1; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 0;
					continue;
				}
				dp[i][j] = grid[i - 1][j - 1] + Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		return dp[m][n];

	}