经典动态规划问题

>1.最大子序和问题
//找到整数数组nums的具有最大和的连续子数组（子数组最少包含一个元素）并返回其最大和
    public int maxSubArray(int[] nums) {
        //动态规划思路：
        //dp[i]代表从数组的开始位置到下标为i的和的最大值
        //dp[i] = Math.max(dp[i - 1], dp[i - 1] + nums[i])
        //上一行即判断：每一次dp[i]的时候要不要加上前面的i-1个（即dp[i-1]有没有可能是负的）
        //针对nums = {-2,1,-3,4,-1,2,1,-5,4}来说
        //nums[i]  -2  1  -3  4  -1  2  1  -5  4  
        //dp[i]    -2  1  -2  4   3  5  6  1   5
        //res     MIN  1   1  4   4  5  6  6   6

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


>2.爬楼梯问题
//共n阶台阶，每次可走1阶或2阶，问有多少种走法
    public int climbStairs(int n) {
        //定义dp[i]为走到第i阶的路径数，由于每一步可走1阶或2阶
        //显然dp[i]与dp[i - 1]、dp[i - 2]有关，转移方程如下：
        //dp[i] = dp[i - 1] + dp[i - 2]

        if (n == 1) return 1;
        if (n == 2) return 2;

        int[] dp = new int[n + 1];//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];
        // return n == 1 ? 1 : (n == 2 ? 2 : (climbStairs(n - 1) + climbStairs(n - 2)));
        //上面一行的递归方法时间复杂度比动态规划高！！超时！！！！
    }

//思考：如果每一步可走1阶、2阶或3阶，又将会有多少种走法呢？
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i- 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

>2.1类似问题还有：leetcode.62 不同路径问题：
leetcode.62：从一个m*n的网格的左上角走到右下角，一共有多少种走法（规定每次只能向下或向右走）
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        //return uniquePaths(m, n - 1) + uniquePaths(m - 1, n);//直接递归，运行超时！！！
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][0] = dp[0][j] = 0;
                dp[i][1] = dp[i][j] = 1;
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}