3.动态规划.题目2

题目

17.单词拆分

题目链接
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。提示：1 <= s.length <= 300；1 <= wordDict.length <= 1000；1 <= wordDict[i].length <= 20
暴力解法：回溯法参考-分割回文串，这是枚举分割后的所有子串，判断是否回文。——要回看一下这道题目。

private:
    bool backtracking(const std::string& s, const std::unordered_set<std::string>& wordset, std::vector<bool>& memory, int startindex){
        if(startindex >=s.size()) return true;
        // 递归的过程中有很多重复计算(记忆化递归)——使用memory数组保存每次计算的以startIndex起始的计算结果，
        // 如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果
        if(!memory[startindex]) return memory[startindex];
        for(int i=startindex; i<s.size(); i++){
            std::string word = s.substr(startindex, i-startindex+1);
            if(wordset.find(word)!=wordset.end() && backtracking(s, wordset, memory, i+1)) return true;
        }
        memory[startindex]=false;
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        std::unordered_set<std::string> wordset(wordDict.begin(), wordDict.end());
        std::vector<bool> memory(s.size(), 1);  // 1表示初始值
        return backtracking(s, wordset, memory, 0);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这个时间复杂度其实也是：O(2^n)

动态规划：字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词，说明就是一个完全背包，
1.dp[i]数组定义： 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词
2.递推关系：如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true；因此递推公式是dp[i] = s[j,i] in wordDict && dp[j]==true, true: false;
3.初始化：0下标，那么dp[0]就是递推的根基，dp[0]一定要为true；非0下标，初始化为false。
4.遍历顺序：这题目是对于word:wordDict 有排序要求的，所以采用的是外层——背包，内层——物品的遍历顺序。

    bool wordBreak(string s, vector<string>& wordDict) {
        std::unordered_set<std::string> wordset(wordDict.begin(), wordDict.end());
        std::vector<bool> dp(s.size()+1, false);
        dp[0]=true;
        for(int i=1; i<=s.size(); i++){ // 背包
            for(int j=0; j<i; j++){ // 物品
                std::string word = s.substr(j, i-j);
                if(wordset.find(word)!=wordset.end() && dp[j]){
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n^3)，因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）； 空间复杂度：O(n）

---

18.打家劫舍

题目链接
每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。举例-输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
1.dp[i]数组定义：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]；
2.递推关系：如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i]，如果不偷第i房间，那么dp[i] = dp[i - 1]，然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。
3.初始化：从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]，从dp[i]的定义上来讲，dp[0]一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])
4.遍历顺序：dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历。

    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        std::vector<int> dp(nums.size());
        dp[0]=nums[0];
        dp[1]=max(nums[0], nums[1]);
        for(int i=2; i<nums.size(); i++){
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[nums.size()-1];
    }
1
2
3
4
5
6
7
8
9
10
11

---

19.打家劫舍2

题目链接
相较于18题，这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。（首尾不能相邻），唯一区别就是成环了，分为以下几种清苦那个
1.情况一：考虑不包含首尾元素
2.情况二：考虑包含首元素，不包含尾元素
3.情况三：考虑包含尾元素，不包含首元素
其实按照遍历顺序，情况二，三就包括情况一的情况了

    int robrange(std::vector<int>& nums, int startindex, int endindex){
        if(endindex==startindex) return nums[startindex];
        std::vector<int> dp(nums.size());
        dp[startindex] = nums[startindex];
        dp[startindex+1] = max(nums[startindex], nums[startindex+1]);
        for(int i=startindex+2; i<=endindex; i++){
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[endindex];
    }
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        int res1 = robrange(nums, 0, nums.size()-2);
        int res2 = robrange(nums, 1, nums.size()-1);
        return max(res1, res2);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度: O(n);空间复杂度: O(n)
这道题目的特殊之处在于对于物品的遍历范围多了一个staridnex，endindex的范围界定，分情况去分别遍历得到两个最大值，再取其中较大值。

---

20.打家劫舍3

题目链接
这次所偷窃的房屋布局类似二叉树的结构，除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）.
暴力解法：后序遍历递归法，父节点需要子节点的val值来计算，并且使用记忆化递推的方法改善普通回溯的超时问题，使用一个map把计算过的结果保存一下，这样如果计算过孙子了，那么计算孩子的时候可以复用孙子节点的结果。

    // 记录已经遍历过的对应子节点的值
    std::unordered_map<TreeNode*, int> umap;
    int rob(TreeNode* root) {
        if(root==nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return root->val;
        if(umap[root]) return umap[root]; // 若umap对应root已经有值，则可直接返回

        // 后序遍历-需要递归函数的返回值来做下一步计算（对上一个节点）
        int val1 = root->val;
        if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
        if(root->right) val1 += rob(root->right->left) + rob(root->right->right);
        int val2 = rob(root->left) + rob(root->right);
        umap[root] = max(val1, val2);
        return max(val1, val2);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n)；空间复杂度：O(log n)，算上递推系统栈的空间
以上的暴力回溯法，其实对一个节点 偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。
动态规划法：这道题目算是树形dp的入门题目，因为是在树上进行状态转移，遍历树形数据，需要使用到递归函数
1.递归函数参数和返回值：求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组，输入参数则是当前二叉树节点指针，下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱
2.终止条件：遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回；
3.遍历顺序：必须使用后序遍历；
4.单层递归逻辑：如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]；如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1])；最后当前节点的状态就是{val2, val1}；

    std::vector<int> robtree(TreeNode* root){
        if(root==nullptr) return std::vector<int>{0,0};
        std::vector<int> left   = robtree(root->left);
        std::vector<int> right  = robtree(root->right);
        int val1 = root->val + left[0] + right[0]; // 选择root
        int val2 = max(left[0], left[1])+max(right[0], right[1]); // 不选择root
        return {val2, val1};
    }
    int rob(TreeNode* root) {  
        std::vector<int> res = robtree(root);
        return max(res[0], res[1]);
    }
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)，每个节点只遍历了一次；空间复杂度：O(log n)，算上递推系统栈的空间
所以树形DP也没有那么神秘！只不过平时我们习惯了在一维数组或者二维数组上推导公式，一下子换成了树，就需要对树的遍历方式足够了解！

---

21.买卖股票的最佳时机-简单

题目链接
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。试图获取最大利润。
暴力解法：两层for循环遍历，一层买入，一层卖出，记录最大值；
贪心算法：因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值；
动态规划：
1.dp[i]数组定义：需要使用二维dp数组；dp[i][0] 表示第i天持有股票所得最多现金，dp[i][1] 表示第i天不持有股票所得最多现金
2.递推关系：1.如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来：第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]；第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]；dp[i][0] = max(dp[i - 1][0], -prices[i])。2.如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来：第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]；第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]；dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])。
3.初始化：由递推公式可以看出，后序dp数组基础都是要从dp[0][0]和dp[0][1]推导出来。对于0下标：dp[0][0]表示第0天持有股票，即dp[0][0] -= prices[0]，dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0。
4.遍历顺序：从前向后遍历。

    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len==0) return 0;
        std::vector<std::vector<int>> dp(len, std::vector<int>(2));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for(int i=1; i<len; i++){
            dp[i][0] = max(dp[i-1][0], -prices[i]); // 持有股票
            dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0]); // 不持有股票
        }
        return dp[len-1][1];
    }
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)；空间复杂度：O(n)；
也可以使用一个二维的滚动数组作为dp数组进行覆盖

    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len==0) return 0;
        std::vector<std::vector<int>> dp(2, std::vector<int>(2));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for(int i=1; i<len; i++){
            dp[i%2][0] = max(dp[(i-1)%2][0], -prices[i]); // 持有股票
            dp[i%2][1] = max(dp[(i-1)%2][1], prices[i]+dp[(i-1)%2][0]); // 不持有股票
        }
        return dp[(len-1)%2][1];
    }
1
2
3
4
5
6
7
8
9
10
11
12

---

22.买卖股票的最佳时机2-中等

题目链接
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）注意：你不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）
贪心算法：计算每天交易能获取的最大利润
动态规划：
1.需要使用二维dp数组；dp[i][0] 表示第i天持有股票所得最多现金，dp[i][1] 表示第i天不持有股票所得最多现金
递推关系：第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]；第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来：第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]，第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]。这正是因为本题的股票可以买卖多次！ 所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。

    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        std::vector<std::vector<int>> dp(2, std::vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1; i<len; i++){
            dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]-prices[i]);
            dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0]+prices[i]);
        }
        return dp[(len-1)%2][1];
    } 
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(n)；空间复杂度：O(1)

---

股票问题总结

从买卖一次到买卖多次，从最多买卖两次到最多买卖k次，从冷冻期再到手续费，最后再来一个股票大总结，可以说对股票系列完美收官了。最基础的买卖一次，到买卖多次，到买卖2次，到买卖k次，最后变种是设置冷冻期，手续费。