频率很高的笔试题--动态规划类型(上)

淩亂°似流年 2023-06-25 15:25 19阅读 0赞

### 动态规划解题算法 ###

*   *   *  1、最长上升子序列
         *  2、零钱兑换
         *  3、最大子序列之和
         *  4、单词拆分
         *  5、比特位计数
         *  6、整数拆分
         *  7、1 最大正方形
         *   *  2 最大子矩阵
         *  8、打家劫舍 II
         *  9、最长有效括号
         *  10、机器人达到指定位置方法数

### 1、最长上升子序列 ###

给定一个无序的整数数组，找到其中最长上升子序列的长度

> 示例  
> 输入: \[10,9,2,5,3,7,101,18\]  
> 输出: 4  
> 解释: 最长的上升子序列是 \[2,3,7,101\]，它的长度是 4

方法一：典型的动态规划，dp\[i\] 表示到第 i 位时最长上升子序列的长度，为了更新 dp\[i\]，需要找到以 num\[i\] 为最后一个元素的所有上升子序列，求出最长的长度

状态转移方程为：`p[i] = max(dp[j]) + 1` , 其中 `0 < j < i` , 且 `nums[i] > nums[j]`，若不存在 `nums[i] > nums[j]` , 其中`0 < j < i` , 则 `dp[i] = 1`

def lengthOfLIS(self, nums: List[int]) -> int:
            if not nums:
                return 0
            n = len(nums)
            dp = [1]*len(nums)
            for i in range(1,n):
                cout = 0
                for j in range(i):
                    if nums[j]<nums[i]:
                        cout = max(dp[j],cout)
                if cout:
                    dp[i] = cout+1
            return max(dp)

C++ 写法

int lengthOfLIS(vector<int>& nums) { 
            int n = nums.size();
            if(n==0){ 
                return 0;
            }
            vector<int>dp(n,1);
            int resmax = 1;
            for(int i = 1;i<n;++i){ 
                int temp = 0;
                for(int j = 0;j<i;++j){ 
                    if(nums[j]<nums[i]){ 
                        temp = max(temp,dp[j]);
                    }
                }
                if(temp){ 
                    dp[i] = temp + 1;
                }
                resmax = max(resmax,dp[i]);
            }
            return resmax;
        }

方法二：上面时间复杂度为O(N2)，利用二分查找可以优化时间复杂度为 O(N\*log2N)

def lengthOfLIS(self, nums: List[int]) -> int:
            dp  = [0] * len(nums)
            res = 0
            for num in nums:
                left, right = 0, res
                while left < right:
                    mid = (left + right) // 2
                    # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可
                    if dp[mid] < num:
                        left = mid + 1
                    else:
                        right = mid
                dp[left] = num
                if right == res:
                    res += 1
            return res

### 2、零钱兑换 ###

给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1

> 示例1  
> 输入: coins = \[1, 2, 5\], amount = 11  
> 输出: 3  
> 解释: 11 = 5 + 5 + 1

> 示例2  
> 输入: coins = \[2\], amount = 3  
> 输出: -1

错误思路：先将 coins 排序，然后依次取出coins 最后一个数字和amount 比较，如果大于amount 则弹出最后一个元素，如果小于amount 则将最后一个元素添加到返回列表中，最后看amount 是否为0，如果等于 0 则返回列表长度，否则返回 -1

正确思路：利用动态规划，从 1 到 amount 这个范围，需要一个一个去判断它最小的个数，dp\[i\] 表示凑成总金额 i 需要的最少硬币个数

如例 1 中 coins=\[1,2,5\]，dp\[1\] , dp\[2\] 和 dp\[5\] 都等于 1，因为用相应金额的一枚硬币就能组成 i

对于其他的 i ，例如 i = 11

> **dp\[11\] = min(dp\[11-1\], dp\[11-2\], dp\[11-5\])+1**

dp\[i\] 只有这两种更新方式 ，有可能 amount 无法用 coins 里的硬币构成，那么，初始化每个 dp\[i\] 的时候都为 amount,若 dp\[amount\] > amount 返回 -1

C++ 版本

int coinChange(vector<int>& coins, int amount) { 
            vector<int>dp(amount+1);
            sort(coins.begin(),coins.end());
            unordered_map<int,int>um;
            for(auto&e: coins){ 
                um[e] = 1;
            }
            for(int i = 1;i<amount+1;++i){ 
                if(um[i]){ 
                    dp[i] = 1;
                    continue;
                }
                int min_val = amount;
                for(int j = 0;j<coins.size();++j){ 
                    if(i>=coins[j]){ 
                        min_val = min(min_val,dp[i-coins[j]]);
                    }
                }
                dp[i] = min_val+1;
            }
            if(dp[amount]>amount){ 
                return -1;
            }
            return dp[amount];
        }

方法二：

int coinChange(vector<int>& v, int aim,int n) { 
        vector<int>dp(aim+1);
        // dp[i] 表示到达 i 目标值的最小货币个数
        for(int i = 1;i<aim+1;++i){ 
            int min_val = aim;
            for(int j = 0;j < n;++j){ 
                if(i >= v[j]){ 
                    min_val = min(min_val,dp[i-v[j]]);
                }
            }
            dp[i] = min_val + 1;
        }
        if(dp[aim] > aim){ 
            return -1;
        }
        return dp[aim];

### 3、最大子序列之和 ###

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

> 示例  
> 输入: \[-2,1,-3,4,-1,2,1,-5,4\],  
> 输出: 6  
> 解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6

**动态规划解题**：temp \[i\]表示到第i为时由第i个数为序列最后一个数时的最大和，若temp \[i-1\]>0,果断连起来,加 temp\[i\]；反之，以当前数位序列的第一个数；每一位时都记录到目前为止最大的子序列和。

C++ 参考代码

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            if(nums.empty()) return 0;
            int n = nums.size();
            vector<int>dp(n,0);
            dp[0] = nums[0];
            int ans = dp[0];
            for(int i = 1;i<n;++i){ 
                // 如果前 i 和数字之和大于0，则加当前元素
                if(dp[i-1]>0){ 
                    dp[i] = dp[i-1]+nums[i];
                }else{ 
                    // 如果小于0则把当前元素赋值给dp
                    dp[i] = nums[i];
                }
                ans = max(ans,dp[i]);
            }
            return ans;
        }
    };

方法二：可以不保存前 i 个元素之和，直接进行当前元素与最大值的判断，并且时刻更新最大值，最后返回，空间复杂度为O(1)

C++ 参考代码

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            if(nums.empty()) return 0;
            int n = nums.size();
            int temp = nums[0];
            int ans = temp;
            for(int i = 1;i<n;++i){ 
                if(temp > 0){ 
                    temp += nums[i];
                }else{ 
                    temp = nums[i];
                }
                ans = max(ans,temp);
            }
            return ans;
        }
    };

### 4、单词拆分 ###

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词,  
你可以假设字典中没有重复的单词

> 示例1  
> 输入: s = “leetcode”, wordDict = \[“leet”, “code”\]  
> 输出: true  
> 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

> 示例2  
> 输入: s = “applepenapple”, wordDict = \[“apple”, “pen”\]  
> 输出: true  
> 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。  
> 注意你可以重复使用字典中的单词。

> 示例3  
> 输入: s = “catsandog”, wordDict = \[“cats”, “dog”, “sand”, “and”, “cat”\]  
> 输出: false

方法一：通过两个下标对字符串进行控制，如果当前字符串s\[j:i\]存在于 wordDict 中，把右下标加到 temp 中，那么下次就可以从 i 下标为起点（左下标）来判断字符串…这样，temp 最后一个值一定就是字符串长度，否则就无法分割

def wordBreak(s, wordDict):
            n = len(s)
            temp = [0]
            for i in range(n+1):
                for j in temp:
                    if s[j:i] in wordDict:
                        temp.append(i)
                        break
            return temp[-1] == n

方法二：利用 C++ 容器中 unordered\_set 对字符串进行分割和查找

bool wordBreak(string s, vector<string>& wordDict) { 
            vector<bool>dp(s.size()+1,false);
            unordered_set<string>m(wordDict.begin(),wordDict.end());
            dp[0] = true;
            for(int i = 0;i < s.size()+1;++i){ 
                for(int j = 0;j<i;++j){ 
                    if(dp[j] && m.find(s.substr(j,i-j))!=m.end()){ 
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.size()];
        }

进阶：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子

说明：  
分隔时可以重复使用字典中的单词。  
你可以假设字典中没有重复的单词。

> 示例1  
> 输入:  
> s = “catsanddog”  
> wordDict = \[“cat”, “cats”, “and”, “sand”, “dog”\]  
> 输出:  
> \[  
> “cats and dog”,  
> “cat sand dog”  
> \]

> 示例2  
> 输入:  
> s = “pineapplepenapple”  
> wordDict = \[“apple”, “pen”, “applepen”, “pine”, “pineapple”\]  
> 输出:  
> \[  
> “pine apple pen apple”,  
> “pineapple pen apple”,  
> “pine applepen apple”  
> \]  
> 解释: 注意你可以重复使用字典中的单词。

> 示例3  
> 输入:  
> s = “catsandog”  
> wordDict = \[“cats”, “dog”, “sand”, “and”, “cat”\]  
> 输出:  
> \[\]

先判断是否可以分割，然后进行回溯，有一定的难度

class Solution { 
    public:
    	// 判断是否可以分割
        bool wordBreak2(string s, vector<string>& wordDict) { 
            vector<bool>dp(s.size()+1,false);
            unordered_set<string>m(wordDict.begin(),wordDict.end());
            dp[0] = true;
            for(int i = 0;i < s.size()+1;++i){ 
                for(int j = 0;j<i;++j){ 
                    if(dp[j] && m.find(s.substr(j,i-j))!=m.end()){ 
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.size()];
        }
        // 进行回溯
        void helper(string s, int l, int r){ 
            if(l>r){ 
                string str;
                for(int i=0; i<path.size()-1; i++)
                    str = str + path[i] + " ";
                str += path.back();
                ans.push_back(str);
                return ;
            }
            // i是截取字符串的长度
            for(int i=1; i<=r-l+1; i++){ 
                string tmp = s.substr(l, i);
                if(sstr.find(tmp) != sstr.end()){ 
                    path.push_back(tmp);
                    helper(s, l+i, r);
                    path.pop_back();
                }
            }  
        }
        vector<string> wordBreak(string s, vector<string>& wordDict) { 
            if(!wordBreak2(s, wordDict)){ 
                return ans;
            }
            sstr = unordered_set<string>(wordDict.begin(), wordDict.end());
            helper(s, 0, s.size()-1);
            return ans;
        }
    private:
        unordered_set<string>sstr;
        vector<string>ans;
        vector<string>path;
    };

### 5、比特位计数 ###

给定一个非负整数 num ，对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回

> 示例1  
> 输入: 2  
> 输出: \[0,1,1\]

> 示例2  
> 输入: 5  
> 输出: \[0,1,1,2,1,2\]

方法一：常规思路，从 0 到 n 计算每一个数的1个数，计算1的个数可以用 & 符号来计算.

def countBits(self, num: int) -> List[int]:
            res = []
            for n in range(num+1):
                temp = n
                count = 0
                while temp:
                    temp = temp&(temp-1)
                    count+=1
                res.append(count)
            return res

方法二：可以用一个动态规划的思路，当前值的二进制1的个数等于当前值 & 前一个值 +1

> 例1： 4 的二进制1个数为1，和 3 进行 & 操作后，1的个数变为1，最后再加1就可以了

> 例2：6 的二进制 1 个数为 2 ,和 5 进行 & 操作，1的个数变为1，然后再加1就可以了

python 写法

def countBits(self, num: int) -> List[int]:
            res = [0]*(num+1)
            for i in range(1,num+1):
                res[i] =res[i&(i-1)]+1
            return res

c++ 写法

vector<int> countBits(int num) { 
            vector<int>dp(num+1);
            for(int i = 1;i < num + 1;++i){ 
                dp[i] = dp[i&(i-1)]+1;
            }
            return dp;
        }

### 6、整数拆分 ###

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积

> 示例1  
> 输入: 2  
> 输出: 1  
> 解释: 2 = 1 + 1, 1 × 1 = 1

> 示例2  
> 输入: 10  
> 输出: 36  
> 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

思路：动态规划  
当 n<=3 时，返回 n-1，当 n>=4 时

**最大乘积一定是由 k 个 2 和 m 个 3 组成的**(这个是重点)，因为让每个因子尽可能的相等，乘积是最大的，就类型与计算正方体的面积

dp\[i\] 表示 i 拆分后的最大乘积，其中i>=4， 为了dp\[4\],dp\[5\],dp\[6\]能正常计算，需要初始化dp\[0\]=dp\[1\]=0,dp\[2\]=2,dp\[3\]=3

状态转移矩阵为`dp[i] = max(dp[i-2] * 2 , dp[i-3] * 3)`

def integerBreak(self, n: int) -> int:
            if n<4:
                return n-1
            dp = [0]*(n+1)
            dp[1],dp[2],dp[3] = 1,2,3
            for i in range(4,n+1):
                dp[i] = max(dp[i-2]*2,dp[i-3]*3)
            return dp[n]

### 7、1 最大正方形 ###

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

> 示例  
> 输入:  
> 1 0 1 0 0  
> 1 0 1 1 1  
> 1 1 1 1 1  
> 1 0 0 1 0  
> 输出: 4

动态规划：初始化一个二维列表，赋初值为0  
动态转移方程是：`res[i][j] = min(res[i-1][j-1],res[i-1][j],res[i][j-1])+1`  
最大的 res\[i\]\[j\] 是边数，最后返回平方值

> 案列：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]

C++ 写法

int maximalSquare(vector<vector<char>>& matrix) { 
            int row = matrix.size();
            if(row == 0){ 
                return 0;
            }
            int col = matrix[0].size();
            vector<vector<int>>dp(row+1,vector<int>(col+1,0));
            int r = 0;
            for(int i = 1;i<row+1;++i){ 
                for(int j = 1;j<col+1;++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;
                        r = max(r,dp[i][j]);
                    }
                }
            }
            return r*r;
        }

#### 2 最大子矩阵 ####

给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。

思路：把题转换为柱状图的最大矩形面积，然后利用单调栈

int largest(vector<int>&dp){ 
        dp.push_back(0);
        stack<int>s;
        int res = 0;
        // 单调栈
        for(int i = 0;i<dp.size();++i){ 
            // 如果当前元素比栈顶元素小则进行计算
            while(!s.empty() && dp[s.top()]>dp[i]){ 
                int t = s.top();
                s.pop();
                int weight = s.empty()?i:(i-s.top()-1);
                res = max(res,weight * dp[t]);
            }
            s.push(i);
        }
        return res;
    }
    
    int main(){ 
        int n,m;
        cin>>n>>m;
        vector<vector<int>>v(n,vector<int>(m));
        for(int i = 0;i<n;++i){ 
            for(int j = 0;j<m;++j){ 
                cin>>v[i][j];
            }
        }
        // 本题可以转换为求柱状图中的最大矩阵
        vector<int>t(m);
        int ans = 0;
        for(int i = 0;i<n;++i){ 
            for(int j = 0;j<m;++j){ 
                if(v[i][j] == 1){ 
                    t[j] +=1;
                }else{ 
                    t[j] = 0;
                }
            }
            // largest 表示的是前 i 行对应的最大矩阵
            ans = max(ans,largest(t));
        }
        cout<<ans<<endl;
        return 0;
    }

### 8、打家劫舍 II ###

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额

> 示例1  
> 输入: \[2,3,2\]  
> 输出: 3  
> 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的

> 示例 2  
> 输入: \[1,2,3,1\]  
> 输出: 4  
> 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）  
> 偷窃到的最高金额 = 1 + 3 = 4

思路：典型的动态思路，dp\[i\] 代表到目前偷盗的金额，转义方程是 `dp[i] = max(dp[i-2]+nums[i],dp[i-1])`

int rob(vector<int>& nums) { 
            int n = nums.size();
            if(n==0){ 
                return 0;
            }
            if(n==1){ 
                return nums[0];
            }
            if(nums.size()==2){ 
                return max(nums[0],nums[1]);
            }
            vector<int>dp(nums.size(),0);
            dp[0] = nums[0];
            // 由于只有两个值，所以选取最大值
            dp[1] = max(nums[0],nums[1]);
            for(int i = 2;i < n;++i){ 
                dp[i] = max(dp[i-1],nums[i]+dp[i-2]);
            }
            return dp[n-1];
        }

方法二：空间复杂度为O(1)，dp1 代表当天偷的最大值，dp2 代表当天没偷的最大值.(不太好理解，因为只保存了最后一次的金额)

int rob(vector<int>& nums) { 
            int dp1 = 0;
            int dp2 = 0;
            for(auto&e:nums){ 
                int temp = dp1;
                dp1 = max(dp1,dp2+e);
                dp2 = temp;
            }
            return dp1;   
        }

进阶：如果第一家和最后一家是相邻的，那么情况又是怎么样的？

如果总户数小于三家，则选择其中最大的一家，因为第一家和最后一家是连接起来的

int rob(vector<int>& nums) { 
            if(nums.size()==0){ 
                return 0;
            }      
            if(nums.size()==1){ 
                return nums[0];
            }
            vector<int>dp1(nums.size(),0);
            vector<int>dp2(nums.size(),0);
            dp1[0] = 0;
            dp1[1] = nums[0];  
            for(int i=2;i<nums.size();++i){ 
                dp1[i] = max(dp1[i-1],nums[i-1]+dp1[i-2]);
            }
            dp2[0] = 0;
            dp2[1] = nums[1]; 
            for(int i = 2;i<nums.size();++i){ 
                dp2[i] = max(dp2[i-1],nums[i]+dp2[i-2]);
            }
            return max(dp1[nums.size()-1],dp2[nums.size()-1]);
        }

### 9、最长有效括号 ###

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

> 示例1  
> 输入: “(()”  
> 输出: 2  
> 解释: 最长有效括号子串为 “()”

> 示例2  
> 输入: “)()())”  
> 输出: 4  
> 解释: 最长有效括号子串为 “()()”

思路：dp\[i\]表示以第i个字符结尾的有效括号的最长长度

对于（ ）（（ ））  
i=4: dp = \[0,2,0,0,2,0\]  
i=5: dp = \[0,2,0,0,2,6\]  
dp\[5\] = 2 + dp\[5-dp\[5-1\]-2\]

解释：dp\[i\] 和dp\[i-1\]有关，还和dp\[i-dp\[i-1\]-2\]有关，没有第5位的‘）’时， 第2位的‘（’把0-4的字串分成了两端有效括号，但有了第5位的‘）’时，激活了这两段之间的连接，使之形成一整段有效括号

当s\[i\] == ‘(’:dp\[i\] = 0  
当s\[i\] == ‘)’,并能找到前半个‘（’:  
**状态转移方程：dp\[i\] = dp\[i-dp\[i-1\]-2\] + 2+ dp\[i-1\]**

def longestValidParentheses(self, s):
        max_len = 0
        len_s = len(s)
        dp = [0]*len_s
        for i in range(1,len_s):
            if s[i] ==')':
                if i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(':                  
                    dp[i] = dp[i-dp[i-1]-2] + 2+ dp[i-1]
                    max_len = max(max_len, dp[i])            
        return max_len

### 10、机器人达到指定位置方法数 ###

假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模

思路：走到当前位置的和是前一个位置和 + 后一个位置和，然后进行迭代更新

参考 code

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main(){ 
        int n,m,k,p;
        int mod = 1e9 + 7;
        cin>>n>>m>>k>>p;
        // n 代表的是位置个数，m 代表的是起始位置，k 代表走的步数，p 代表最终位置
        vector<int>dp(n+2);
        dp[m] = 1;
        vector<int>cur(n+2);
        for(int i = 0;i < k;++i){ 
            for(int j = 1; j<=n;++j){ 
                cur[j] = (dp[j-1] + dp[j+1])%mod;
            }
            for(int t = 1;t <= n;++t){ 
                dp[t] = cur[t]; 
            }
        }
        cout<<cur[p]<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191215205309332.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70