【剑指offer第八天】动态规划(简单)

刺骨的言语ヽ痛彻心扉 2022-09-11 09:21 132阅读 0赞

#### 第一题 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]  
斐波那契数列，采用递归会超时。因为递归会重复的计算之前已经计算过的子问题，采用动态规划的算法，记录之前算过的数据。

class Solution { 
        public int fib(int n) { 
            if(n == 0){ return 0;}
            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];
        }
    }

#### 第二题 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
与斐波那契数列问题类似，青蛙跳到最后一级台阶上时只有两种跳法，一种是跳一阶，另一种是跳两阶。用dp数组来保存之前的跳法种类。那么dp\[n\]的跳法总数为dp\[n-1\]+dp\[n-2\]，前两种跳法的总和。  
dp\[0\]=1,dp\[1\]=1。

class Solution { 
        public int numWays(int n) { 
            if(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];
        }
    }

#### 第三题 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
计算股票的最大利润，只买卖一次，记录股票的最低价格，不断更新最大利润值。可以不使用dp数组，采用一个变量max来记录最大利益，降低空间复杂度。

class Solution { 
        public int maxProfit(int[] prices) { 
            //股票的最大利润
            int l = prices.length;
            int []dp = new int[l];
            if(l < 1){ return 0;}
            int res = 0,min = prices[0];
            for(int i = 1;i < l;i++){ 
                min = Math.min(min,prices[i]);
                dp[i] = Math.max(dp[i - 1],prices[i]-min);
            }
            return dp[l-1];
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b18d6d1d3e2f4aeabfa5d7412fca91c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8bbc8c26e75b4a7dbf9edf89d5594aec.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ca006a332cc347078714bcfc89f6f9e9.png