「算法刷题」回溯算法的排列和序列问题

​ 本博客是记录作者做回溯算法的和排列和序列问题的中等难度题的笔记。

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
46	全排列（中等难度）			https://leetcode-cn.com/problems/permutations/
47	全排列II（中等难度）			https://leetcode-cn.com/problems/permutations-ii/
491	递增子序列（中等难度）			https://leetcode-cn.com/problems/increasing-subsequences/
332	重新安排行程（中等难度）			https://leetcode-cn.com/problems/reconstruct-itinerary/

46 全排列（中等难度）

这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。

代码如下：

int rob(vector<int>& nums) {
        /*输入一个数组，输出一个整数*/
        if(nums.size()==1){
            return nums[0];
        }
        vector<int> dp(nums.size());//dp[i]表示加上第i个房屋后一共可以盗窃的最大金额
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        // 推导dp数组
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        
        return dp[nums.size()-1];
    }