动态规划-爬楼梯

1.以爬楼梯问题为例，总结动态规划的步骤：

第一步：定义dp数组（可能时一维数组，也可能是二维数组），这一步需要确定两个问题：

（1）dp[i]或者dp[i][j]是什么含义（比如在爬楼梯问题中，dp[i]表示到达第i层有多少种爬法）

（2）到底开多大的空间，你搞懂了第一个问题dp[i]或者dp[i][j]是什么含义，就知道到底要开多大的空间了，由于在爬楼梯问题中，dp[i]表示到达第i层有多少种爬法，你最后求的是到达第n层所需要的爬法数，所以最后要返回的是dp[n]，所以显然要开n+1大小的数组，这样才能有dp[n](如果你只开n大小的数组，那么最后只能返回dp[n-1]

第二步：初始化这个数组中的部分值

dp[0]题目已经给了等于1

dp[1]就是到达第一层有几种爬法，显然dp[1]=1

第三步：/写出状态转移方程确定dp数组中其他位置元素的值

爬楼梯问题：爬到第n层有可能是从第n-1层然后跨一层到达第n层的，也可能时从第n-2层然后跨两层到达第n层的

青蛙跳台阶：力扣

class Solution 
{
    public int numWays(int n) 
    {
        if (n == 0) return 1;
        if (n == 1) return 1;
 
        //定义一个dp数组，dp[i]表示到达第i层有多少种爬法
        int[] dp = new int[n + 1];
 
        //初始化dp数组
        dp[0] = 1;
        dp[1] = 1;
 
        //写出状态转移方程确定数组中其他位置元素的值
        for (int i = 2; i <= n; i++) 
        {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

爬楼梯：力扣

class Solution
 {
    public int climbStairs(int n) 
    {
        if(n==1)   return 1;
        if(n==2)   return 2;
        ArrayList<Integer> result=new ArrayList();
        result.add(0);
        result.add(1);
        result.add(2);
        for(int i=3;i<=n;i++)
        {
            result.add(result.get(i-1)+result.get(i-2));
        }
        return result.get(n);
    }
}

2.连续子数组的最大和        力扣53

比如数组为nums[]:1，-2，3，10，-4，7，2，-5

以1结尾的所有子数组，以-2结尾的所有子数组，以3结尾的所有子数组.........以7结尾的所有子数组，以2结尾的所有子数组，以-5结尾的所有子数组

开一个数组dp[nums.length],

dp[i]表示以nums[i]结尾的所有子数组中最大和

比如：dp[0]表示以nums[0](也就是1）结尾的所有子数组中最大和，显然dp[0]=1

dp[1]表示以nums[1]（也就是-2）结尾的所有子数组中最大和，显然dp[0]=1

.......

显然dp[i+1]=max(nums[i+1],dp[i]+nums[i+1])

也就是说，dp[i+1]要么就是等于dp[i]加上nums[i+1]，要么就是不要前面的子序列，只要nums[i+1]这个数

class Solution 
{
    public int maxSubArray(int[] nums) 
    {
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for(int i=0;i<nums.length-1;i++)
        {
            dp[i+1]=Math.max(nums[i+1],dp[i]+nums[i+1]);
        }
        Arrays.sort(dp);
        return dp[nums.length-1];
    }
}