动态规划：解决青蛙跳台阶、最大子数组和、最长递增子序列

class Solution {
    public int fib(int n) {
        //动态规划
        if(n==0){
            return 0;
        }
        if(n==1){
           return 1;
        }
        //字符串长度是可以变化的
        int [] dp= new int [n+1];
        dp[0]=0;
        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 numWays(int n) {
        if(n==0 || n==1){
            return 1;
        }
        int [] dp=new int[n+1];
        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 maxSubArray(int[] nums) {
        //动态规划的思路，定义一个dp[],进行对前边数多个数的和进行记录，如果前边数的和>=0,进行求和；如果dp前边的数组小于0，则就是把这个数组放进dp中，不进行求和
        int []dp=new int[nums.length];
        dp[0]=nums[0];
        int max=nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]>=0){
                dp[i]=dp[i-1]+nums[i];
            }else{
                dp[i]=nums[i];
            }
          max=Math.max(max,dp[i]);
        }
        return max;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {

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


    }
}