动态规划的解题思路

动态规划

“动态规划”用于多阶段最优解问题的求解。
关键的思想在「自底向上」和「空间换时间」。
“动态规划”，其实就是找规律，总结公式/方程。
动态规划，类似于数学归纳法。
动态规划，可以使用一维数组，有时也会用到二维数组。

一维数组dp[i] 的动态规划的几个步骤：

• 确定数组dp[i]的下标i以及dp[i]值的含义，比如经典的LeetCode70爬楼梯， 爬到第i层楼梯，有dp[i]种方法；
• 确定动态规划的状态转移方程（递推公式）。比如，爬楼梯的公式：dp[i] = dp[i-1] + dp[i-2];
• dp数组的初始化：初始化值，dp[0]的值是多少 , dp[1]的值又是多少;
• 确定遍历顺序：分析递推顺序应该是从前往后，还是从后往前。还有就是，要从哪一个下标开始遍历；

示例：LeetCode70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

public int climbStairs(int n) {
	if (n <= 0) {
	    return 0;
	}
        //dp数组的初始化
	int[] dp = new int[n + 2];
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
                //确定动态规划的状态转移方程（递推公式）
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

LeetCode53. 最大子数组和

• 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {
    public int maxSubArray(int[] nums) {
        int length=nums.length;
        int[] dp=new int[length];
        //初始值
        dp[0]=nums[0];
        int maxSum=nums[0];
        for(int i=1;i