动态规划 | zhkmxx930 blog

[Leetcode 198] 打家劫舍

解法：一个经典的dp题，从选与不选的角度进行考虑，
$OPT(i)=max\{(OPT(i-2)+arr[i]), OPT(i-1)\}$
终止条件是第0个的时候只有一个可以选，有两个的时候，选二者中大的那个。
参考：动态规划（第2讲第一个demo）

代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        vector<int > dp(nums.size(), 0); //构造dp数组
                
        // dp终止条件
        dp[0] = nums[0];
        dp[1] = max(nums[1], nums[0]);
        
        // 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];
    }
};

[Leetcode 213] 打家劫舍 II

解法：由于有环，那么给他拆分成[0,n-1] 和 [1,n]两个部分进行分别dp，最后取两个区间中取值大的。
代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0],  nums[1]);
        
        vector<int> dp_n_1(nums.size(), 0); //[0,n-1]
        vector<int> dp_n(nums.size(), 0); //[1, n]
        
        dp_n[0] = 0;
        dp_n[1] = nums[1];
        dp_n[2] = max(nums[1], nums[2]);
        
        dp_n_1[0] = nums[0];
        dp_n_1[1] = max(nums[0], nums[1]);
        dp_n_1[2] = max(dp_n_1[1], nums[2]);
        
        for(int i = 2; i<nums.size()-1; i++){
            dp_n_1[i] = max((dp_n_1[i-2] + nums[i]),(dp_n_1[i-1]));
        }
        
        for(int i = 3; i<nums.size(); i++){
            dp_n[i] = max((dp_n[i-2] + nums[i]),(dp_n[i-1]));
        }
        
        return max(dp_n_1[nums.size()-2], dp_n[nums.size()-1]);
                                               
    }
};

[Leetcode 139] 单词拆分

解法(4种)
- 解法一: DFS
- 解法二: 记忆化DFS
- 解法三: bottom up DP
  
  [子问题定义] : DP子问题是从0开始到当前位置的子串是否可分(dp[i] == true?)，当前位置总共有n个可能，所以子问题的个数是n个。
  
  使用hashset转储dict
  
  构建dp数组，默认初始空串是可分的即dp[0]=1,
  
  遍历初始串，验证从前面可分的子串尾部到当前位置的字符串([j为dp[j]==1, i])是否在字典中，如果在字典中则记录当前位置可分
- 解法四: Bottom up DP + max trick
代码:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.cbegin(), wordDict.cend());
        vector<int > dp(s.size()+1, 0); //加1是给空串留位置
        dp[0] = 1;// 空串可分
        
        //解n个子问题
        for(int i = 1; i < s.size()+1; i++){
            for(int j  = 0; j < i; j++){
                // j之前可分，判断j~i这段是不是可分的，可分的话，i的位置记为1
                if(dp[j]){
                    string tmp = s.substr(j, i-j);
                    if(wordSet.find(tmp) != wordSet.end()){
                        dp[i] = 1;
                        break;
                    }
                }
            }
        }
        
        return dp[s.size()];
    }
};

[Leetcode 124] 二叉树中的最大路径和

解法:

找二叉树中的最大路径和，首先要考虑清楚是从上往下找，还是从下往上找，通过观察树的结构，我们发现从下到上最好找。

1、最优子结构
因为树是由一个个更小的结点树组成，所以我们可以把问题分解成一个个更小的树。
当树的结点只有一个时，最大的路径就是他自身，让树的高度为2时，根节点的最大路径为左右结点中的最大值加上根节点本身的值：max(l, r) + root.val，如果左右结点都为负数，还没有自身的值大呢，所以我们取其中的最大值。maxSubSubTree = max(max(l, r) + root.val, root.val)
知道了二叉树的最优左右路径，我们需要比较整体路径，maxSubTree = max(maxSubSubTree, l+r+root.val)。
再将以该结点为根节点的二叉树的最大路径和，和全局的路径和比较，取两者最大值，res = max(res, maxSubTree)
2、重叠子问题
从下往上走，当底层的最优路径找出来了，上一层结点就能直接用下一层的结果,依次向上递推，求解过程都简化成了对若干个个高度为2 的二叉树的操作。当递归完成时，根节点的值就是整颗二叉树的最大路径和。

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res=INT_MIN;
        getMaxPath(root, res);
        return res;
    }
 
    int getMaxPath(TreeNode* root, int &res){
        if(!root) return 0;
        int left = getMaxPath(root->left, res);
        int right = getMaxPath(root->right, res);
        
        //下一级到上一级的最优解
        //下一级的最优解和自身相比，如果下一级没有，或者都为负数，则为自身
        int maxSubSubTree = max(max(left, right) + root->val, root->val);
        
        //表示所考虑是以该结点为根的路径和 
        int maxSubTree = max(maxSubSubTree, root->val + left+ right);
        
        //更新整个树中的最大路径和
        res = max(maxSubTree, res);
        return maxSubSubTree; //返回单个子子树最优解
    }
    
  
};

[Leetcode 128] 最长连续序列

解法：(参考花花酱)

使用hashmap来构建，将数组中的值作为键，连续元素数目作为边界值，并存储在hashmap的连续区域边界节点中。

节点更新有三种情况:
1. 当前元素在hashmap中没有左右邻居，那么该节点的hashmap值为1 ;
2. 当前元素在hashmap中有左或右邻居(只存在一边)，那么该节点的hashmap值为其对应左右边界的连续值加1
3. 当前元素能够桥接两个连续区域，那么该节点的hashmap值可以不关心，但是其左侧的左边界值与右侧部分的右边界值对应加一。

代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> hashMap;
        int res = 0;
        for(auto item: nums){
            if(hashMap.count(item)) continue;
            
            auto it_left = hashMap.find(item-1);
            auto it_right = hashMap.find(item+1);
            //获取当前元素左右的边界值，左右无邻居则对应的l,r 为0
            int l = it_left!=hashMap.end() ? it_left->second : 0;
            int r = it_right!=hashMap.end() ? it_right->second : 0;
            
            //[case3]当前元素能够桥接两个连续区域，那么该节点的hashmap值可以不关心(程序中得填充表示，默认就是跟左右边界相等就行)，但是其左侧的左边界值与右侧部分的右边界值对应加一。
            if(l!=0 && r!=0){
                hashMap[item] = hashMap[item-l] = hashMap[item+r] = r + l + 1;
            }else if(l!=0 && r == 0){ //[case2] 当前元素在hashmap中有左或右邻居(只存在一边)，那么该节点的hashmap值为其对应左右边界的连续值加1
                hashMap[item] = hashMap[item-l] = l + 1;
            }else if(l==0 && r!=0){ //[case2] 当前元素在hashmap中有左或右邻居(只存在一边)，那么该节点的hashmap值为其对应左右边界的连续值加1
                 hashMap[item] = hashMap[item+r] = r + 1;
            }else{ //[case1] 当前元素在hashmap中没有左右邻居，那么该节点的hashmap值为1 <currNodeVal, 1>;
                hashMap[item] = 1;
            }
        }
        // 遍历选择边界值最大的
        for(const auto& item: hashMap){
            res = max(res, item.second);
        }
        return res;
    }
};