【每日一题】LeetCode - 动态规划题目(1)

1. 剑指 Offer 42. 连续子数组的最大和

• (https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)
• 本题关键在于dp[i]表示

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (sum > 0) {
                sum += nums[i];
            }else {
                sum = nums[i];
            }
            if (sum > max) 
                max = sum;
        }
        return max;
    }
}

2. 面试题 08.01. 三步问题

• (https://leetcode-cn.com/problems/three-steps-problem-lcci/)

class Solution {
    public int waysToStep(int n) {
        int first = 1;
        int second = 2;
        int third = 4;
        if(n == 1) return first;
        else if (n == 2) return second;
        else if (n == 3) return third;
        else {
            for(int i = 4; i <=n; ++i) {
                int temp = third;
                third = (int)((first + second + (long)third) % 1000000007);
                first = second;
                second = temp;
            }
        }
        return third;
    }
}

3. 300. 最长递增子序列

• (https://leetcode-cn.com/problems/longest-increasing-subsequence/)
• 这道题的动态规划算法还是挺难想(我是菜鸡)
• $dp[i]$ 表示以第$i$个元素为结尾的递增子序列的最大长度。
• 状态转移方程：对于在第$j$个元素($j<i$)，如果存在$nums[j]<nums[i]$,则$dp[i]$ 至少为$dp[j]+1$，至少的意思是说应该考虑所有的$j$元素，并从中区最大的$dp[j]$。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] lens = new int[nums.length];
        int max = lens[0] = 1;
        for (int i = 1; i < nums.length; ++i) {
            int t_len = 0;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i] && lens[j] > t_len) {
                    t_len = lens[j];
                }
            }
            lens[i] = t_len + 1;
            if (max < lens[i]) max = lens[i];
        }
        return max;
    }
}