动态规划day08

本文主要是介绍动态规划day08，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

714. 买卖股票的最佳时机含手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        //两种状态：持有和不持有  为方便解题统一卖出时候计手续费
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        //最后是亏损的就不买
        return dp[len - 1][1];
    }
}

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length <= 1) return 1;
        int len = nums.length, res = 0;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    //以nums[i]w为结尾的最大递增子序列
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            //保存最大递增子序列
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

674. 最长连续递增序列

// //动态规划
// class Solution {
//     public int findLengthOfLCIS(int[] nums) {
//         if (nums.length == 1) return 1;
//         int len = nums.length, res = 0;
//         int[] dp = new int[len];
//         Arrays.fill(dp, 1);
//         for (int i = 1; i < len; i++) {
//             if (nums[i] > nums[i - 1]) {
//                 dp[i] = dp[i - 1] + 1;
//             }
//             res = Math.max(res, dp[i]);
//         }
//         return res;
//     }
// }

//贪心
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int len = nums.length, res = 1, count = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            if (count > res) res = count;
        }
        return res;
    }
}

参考：programmercarl.com

这篇关于动态规划day08的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！