引言：动态规划介绍

什么时候可以使用动态规划：求最优解问题的时候
动态规划的两个主要问题：最优子结构和重叠子问题，一个最优解它的子结构也必然是最优的，同时利用递归完成问题的时候会出现很多重复计算，此时利用保存子结构的解可以避免很多重复计算。
介绍一些常用的状态转移方程思路：
当给出的问题是一个一位数组的时候：
递归形式：a[i] = max(min){solve[i-1],solve[i-2]...}或者
a[i] = b[i] + max(min){solve[i-1],solve[i-2]...} 亦或者
a[i] = for(j=1:n){max(min){a[i]},solve(i-j)}

1.Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

很经典的一个递归问题，每次能走一步或者两步，求有多少种走上去的方法。

class Solution {
    //结果数组
    int ans[] = new int[1024];
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 0) return 1;
        //如果子结构的最优解已经求出，则直接返回即可
        if(ans[n] > 0){
            return ans[n];
        }
        //保存最优子结构ans[n]，最优解可分为两个解：前一阶梯和前两阶梯的解。
        return ans[n] = climbStairs(n-1) + climbStairs(n-2);
    }
}

2.House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

题目要求：不能选取相邻的两个数据

class Solution {
    //结果数组
    int ans[];

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        ans = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            ans[i] = -1;
        }
        return Math.max(solve(nums.length - 1, nums), solve(nums.length - 2, nums));
    }

    //递归形式动态规划解决
    public int solve(int i, int num[]) {
        if (i == 0) return num[0];
        if (i == 1) return num[1];
        //题目说了不能为0？
        if (ans[i] != -1) {
            return ans[i];
        }
        for (int j = 2; j <= i; j++) {
            ans[i] = Math.max(ans[i], num[i] + solve(i - j, num));
        }
        return ans[i];
    }
}

3.Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int thisSum = 0;
        for(int i = 0;i<nums.length;i++){
            thisSum = Math.max(nums[i],thisSum+nums[i]);
            maxSum = Math.max(thisSum,maxSum);
        }
        return  maxSum;
    }
}