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

动态规划（Dynamic Programming）：解决最值问题

求解动态规划的核心在于穷举，但穷举会出现 [ 重叠子问题 ]，一个问题多次计算导致效率过低，所以设置一个DP table进行优化

这个dp table 中存放的是什么，非常关键，找到他的[ 最优子结构 ]+ [ 状态转移方程 ]

拿 [斐波那契数列 ]举例：

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

思考：为了避免暴力穷举导致的效率低的问题，定义一个数组，将每个f(n)存储起来。

dp[i]的每个值都对应的f(n)。

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];
    }
      
}

解决完斐波那契数列问题，下边的 [ 青蛙跳台阶 ] 问题，有异曲同工之处

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

设跳上n级台阶有 f(n) 种跳法。所有跳法种，青蛙的最后一步只有两种情况；跳上一级台阶或者跳上两级台阶。

最后跳一级台阶时：剩 n-1级台阶，此情况有f(n-1)种跳法

最后跳两级台阶时：剩 n-2级台阶，此情况有f(n-2)种跳法

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];
        
    }
}

力扣第 53题 [ 最大子数组和 ] https://leetcode-cn.com/problems/maximum-subarray/

上次参加【字节跳动面试】，这道题还是挺经典的动态数组规划问题。

思考：看到题目的“最”，立马想到使用动态规划进行解决。

求最有最大和的连续子数组，先设置一个动态链表dp[],dp[i]存放的是最大连续的子数组的和，当dp前边的数字>=0,dp[i]=dp[i-1]+nums[i];当dp[i]<0时，dp[i]=nums[i]

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;
    }
}

下边这道题也是使用的动态规划的思路，值得注意的是dp[i]所代表的含义

力扣第 300 题 [ 最长递增子序列 ] https://leetcode-cn.com/problems/longest-increasing-subsequence/

思路：“最”值问题，使用动态规划进行解决；

定义动态数组dp[],那么这个动态数组中具体存放的是什么呢？

求的是严格递增的子序列的长度，可以把最长子序列的长度放进去；

注：子串是必须连续的，但子序列不一定是连续的（具体的题解可以看力扣官方题解，他讲的挺好的）

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;


    }
}

-------------------------------

依然是整理的labuladong老师的文章，做的读书笔记。https://mp.weixin.qq.com/s/Cw39C9MY9Wr2JlcvBQZMcA

The end

#算法题##实习##笔试题目##笔经##Java#