动态规划

221.最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

解题思路：

• 二维dp,dp[i][j] = 以(i, j)为右下顶点的最大正方形边长。
• matrix[i][j] = 0时，dp[i][j] = 0
• matrix[i][j] = 1时，可以联想到dp[i][j] 与 dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]有关，其中任何一个为0都以为着dp[i][j] = 1
• 可以画一画图，会发现dp[i][j]取决于三者的最小值，递推为dp[i][j] = 三者最小值 + 1
• dp的做题思路是先找到dp的形式，基本就是看题目给的1维2维就知道了，然后想dp代表了什么，之后再想当前位置的dp需要之前哪些信息，想出递推关系。
• 递推关系知道了，最次你也能写记忆化搜索；或者熟练的直接写dp。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        int ans=0;
        for(int i = 0;i < m; i++){
            for(int j = 0;j < n; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else{
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    ans = max(ans, dp[i][j]);
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        return ans*ans;
    }
};

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}

func maximalSquare(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	m, n, max := len(matrix), len(matrix[0]), 0
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if matrix[i-1][j-1] == '1' {
				dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
			}
			if dp[i][j] > max {
				max = dp[i][j]
			}
		}
	}
	return max * max
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

53.最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

解题思路：动态规划经典题目，用sumNum来表示以当前元素结尾的最大子数组和；那么整个数组的最大子数组和就是所有位置的最大子数组和取最大，就可以得到答案。时间复杂度O(n)，空间复杂度O(1)

    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum = max(sum + nums[i], nums[i]);
            ans = max(ans, sum);
        }
        return ans;
    }

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    maxSum := 0
    for i := 0; i < len(nums); i++ {
        dp[i] = nums[i]
        if i == 0 {
            maxSum = dp[i]
            continue
        }
        if dp[i-1] + dp[i] > dp[i] {
            dp[i] += dp[i-1]
        }
        if dp[i] > maxSum {
            maxSum = dp[i]
        }
    }
    return maxSum
}

300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路：

• 这道题两个思路，比较容易想的思路是dp，时间复杂度O(n²),空间复杂度O(n)；还有一个思路是贪心+二分查找，时间复杂度O(nlogn), 空间复杂度O(n)
• 思路一：一维dp
• • dp[i]表示以第i位为末尾的最长严格递增子序列长度。所以得到dp[i]可以遍历0到i - 1，如果nums[j] < nums[i]，就表示可以在以j为底的最长严格递增子序列后续上一位，然后找到最大的j即可。
• 思路二: 贪心
• • 首先贪心的思路是，我们希望它上升的越“慢”越好，我们有一个数组d，d[i]代表长度为i的最长递增子序列末尾元素的最小值，在这个贪心思路里，越长肯定末尾元素更大。
• 如果nums[i] 大于 d.back(),那说明出现了一个更大的最长递增子序列，把nums[i]加进d中。
• 不然就找到nums[i]在d中的位置，即找到d[j - 1] < nums[i] < d[j]，nums[i]就可以替换d[j]让长度为j的最小值末尾元素更小。查找这步用二分。

//思路1，dp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1);
        for(int i = 1;i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int ans=INT_MIN;
        for(auto i:dp){
            ans=max(i,ans);
        }
        return ans;
    }
};
//思路2，贪心，二分查找
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> d;
        d.push_back(nums[0]);
        for(int i = 1; i < n; i++) {
            if(nums[i] > d[d.size() - 1]) {
                d.push_back(nums[i]);
            } else{
                auto p = lower_bound(d.begin(),d.end(),nums[i]);
                *p = nums[i];
            }
        }
        return d.size();
    }
};

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i=1;i<n;i++) {
            for(int j=0;j<i;j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        int maxLen = 1;
        for(int len : dp) {
            if(len > maxLen) maxLen = len;
        }
        return maxLen;
    }
}

func lengthOfLIS(nums []int) int {
    res := 0
    dp := make([]int,len(nums))
    for i:=0;i<len(nums);i++{
        dp[i] = 1
    }
    for i:=1;i<len(nums);i++{
        for j:=0;j<i;j++{
            if nums[i]>nums[j]{
                dp[i] = max(dp[i],dp[j]+1)
            }
        }
    }
    for i:=0;i<len(nums);i++{
        res = max(res,dp[i])
    }
    return res
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

32.最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解题思路：

• 这道题思路是dp,dp[i]代表以i为最后一位，最长有效括号子串的长度。
• 首先如果s[i] = '('时，那么以他为最有一位不可能构成最长有效括号子串，dp[i] = 0
• s[i] = ')'时，可以想到dp[i]应该跟dp[i - 1]有关，因为要组成一对，所以要看left = i - dp[i - 1] + 1这一位是否为'(',如果是，那么dp[i] = dp[i - 1] + 2
• 还应该考虑到left左边一位的最长有效括号，他也能拼一起，所以dp[i] = dp[i - 1] + 1 + dp[left - 1]

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ans = 0;
        //dp表示的是第 i 个位置结尾的有效括号长度
        vector<int> dp(n);
        for(int i = 1; i < n; i++) {
            if(s[i] == '(') {
                continue;
            }
            int leftPos = i - dp[i - 1] - 1;
            if(leftPos < 0) {
                continue;
            } 
            if(s[leftPos] == '(') {
                dp[i] = i - leftPos + 1;
                if(leftPos > 0) {
                    dp[i] += dp[leftPos - 1];
                } 
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if(n==0) return 0;
        int[] dp = new int[n];
        dp[0] = 0;
        int res = 0;
        for(int i=1;i<n;i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = (i>=2? dp[i-2]:0) + 2;
                }else if (i>dp[i-1] && s.charAt(i-dp[i-1]-1) == '('){
                    dp[i] = dp[i-1] + (i-dp[i-1]>=2? dp[i-dp[i-1]-2]:0) + 2;
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}

func longestValidParentheses(s string) int {
    if len(s) == 0 {
        return 0
    }
    longest, n := 0, len(s)
    dp := make([]int, n) // dp[i]是以i结尾的子串的最长有效括号
    dp[0] = 0
    for i := 1; i < n; i++ {
        if s[i] == '(' {
            continue
        }
        if s[i-1] == '(' {
            if i - 2 >= 0 {
                dp[i] = dp[i-2] + 2
            }else {
                dp[i] = 2
            }
        }else {
            if i - dp[i-1] -1 >= 0 && s[i-dp[i-1]-1] == '(' {
                if i - dp[i-1] - 2 >=0 {
                    dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2
                } else {
                    dp[i] = dp[i-1] + 2
                }
            }
        }
        longest = max(dp[i], longest)
    }
    return longest
}

func max (x, y int) int {
    if x > y {
        return x
    }
    return y
}

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

解题思路：

• 可以先想2维dp,dp[i][j]代表以第i位为底，凑成金额为j的最少硬币数。
• 易得要么不拿，即dp[i - 1][j]，要么在dp[i][j - coin[i - 1]]的基础上再拿一个，凑成金额为j。也就是dp[i][j] = min(dp[i - 1][j], dp[i][j - coin[i - 1]])
• 这时候可以画个表，横轴是i，纵轴是j，看一下dp[i][j]的递推式，容易看出来dp[i][j]是可以状态压缩的。
• 每次i往前遍历一位，i之前的dp其实并没有用到，可以把i压缩掉，变成一维dp。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, 1e9);
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= amount; j++) {
                if(j >= coins[i - 1]) {
                    dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
                }
            }
        }
        if(dp[amount] == 1e9) return -1;
        return dp[amount];
    }
};

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for(int i=1;i<=amount;i++) {
            for(int coin : coins) {
                if(i >= coin) {
                    dp[i] = Math.min(dp[i-coin] + 1, dp[i]);
                }
            }
        }
        return dp[amount] == amount+1? -1 : dp[amount];
    }
}

func coinChange(coins []int, amount int) int {
    dp := make([]int,amount+1)
    for i:=0;i<len(dp);i++{
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i:=1;i<=amount;i++{
        for j:=0;j<len(coins);j++{
            if coins[j] <= i{
                dp[i] = min(dp[i],dp[i-coins[j]]+1)
            }
         }
    }
    if dp[amount]>amount{
        return -1
    }
    return dp[amount]
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解题思路：

• 属于dp中的模板题目，dp[i][j]表示text1中第i位和text2中第j位结尾的最长公共子序列。
• 如果text1[i] == text2[j]，那么dp[i][j] = dp[i - 1][j - 1] + 1
• 不然dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
};

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}