LeetCode132双周赛T3，搜索和DP

求出最长好子序列 I

dfs(i,j)表示
以nums[i]结尾的，至多有j对相邻元素不同的最长序列的长度
转移:枚举 p<i，
如果 nums[p]!= nums[i]，就从 dfs(p,j-1)+ 1 转移过来
如果 nums[p]== nums[i]，就从 dfs(p;j)+1 转移过来

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
        int res = 0;
        function<int(int, int)>  dfs = [&](int u, int j){
            if(f[u][j])return f[u][j];
            int len = 0;
            for(int i = u - 1; i >= 0; i --)
            {
                if(nums[i] == nums[u]) len = max(len, dfs(i, j) + 1);
                else if(j > 0)len = max(len,dfs(i, j - 1) + 1 );
            }
            f[u][j] = len;
            return len;
        };
        for(int i = 0; i < nums.size(); i ++)
        {
            res = max(res,dfs(i,k) + 1);
        }
        return res;
    }
};

lambda 说明，[&]表示如果用到外面的变量，传递引用
[]啥也不加，表示如果用到外面变量，复制一个进来
如果写的是递归函数，则需要说明返回值是什么，写的不是递归，可以用auto自动推断

DP的写法

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return 0
        
        # dp[i][j] 表示以 nums[i] 结尾，前面有 j 个不同的最长子序列长度
        dp = [[0] * (k + 1) for _ in range(n)]
        
        # 初始化
        for i in range(n):
            dp[i][0] = 1
        
        max_len = 1
        
        for i in range(1, n):
            for j in range(k + 1):
                for m in range(i):
                    if nums[i] == nums[m]:
                        dp[i][j] = max(dp[i][j], dp[m][j] + 1)
                    elif j > 0:
                        dp[i][j] = max(dp[i][j], dp[m][j - 1] + 1)
                max_len = max(max_len, dp[i][j])
        
        return max_len