11.动态规划

198. 打家劫舍

class Solution {
     public int max(int a, int b) {
        return Math.max(a, b);
    }
        public int rob(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length ; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);
        }
        return dp[nums.length];
    }
}

300. 最长递增子序列

 // 2 1 4 3 4 6 1 7
    int lengthOfLIS(vector<int> &nums) {
        int n = nums.size();
        if (n == 0) { return 0; }
        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            cout << dp[i] << " ";
            //1 1 2 2 3 4 1 5 
        }
        return *max_element(dp.begin(), dp.end());
    }