题目链接：最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

方法一：二维动态规划

class Solution {
public:
    int dp[210][210];
    int minPathSum(vector<vector<int>>& grid) {
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0;j < grid[0].size();j++) {
                if (i-1 >= 0 && j - 1 >= 0) {
                    dp[i][j] = min(dp[i-1][j] , dp[i][j-1]);
                }else if (i-1 >= 0) dp[i][j] = dp[i-1][j];
                else if (j-1 >= 0) dp[i][j] = dp[i][j-1];
                dp[i][j] += grid[i][j];
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

题目链接：不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

方法一：二维动态规划

class Solution {
public:
    int dp[110][110];
    int uniquePaths(int m, int n) {
        for (int i = 1;i <= m;i++) {
            dp[i][1] = 1;
        }
        for (int i = 1;i <= n;i++) {
            dp[1][i] = 1;
        }
        for (int i = 2;i <= m;i++) {
            for (int j = 2;j <= n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

题目链接：路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

方法一：递归

class Solution {
public:
    int rootSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};

题目链接：二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

方法一：层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        int num = 0;
        while (q.size()) {
            int t = q.size();
            //int num;
            while (t--) {
                TreeNode* tmp = q.front();
                q.pop();
                num = tmp->val;
                if (tmp->left != nullptr) q.push(tmp->left);
                if (tmp->right != nullptr) q.push(tmp->right);
            }
            ans.push_back(num);
        }
        return ans;
    }
};

方法二：bfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int size = q.size();
            ans.push_back(q.front()->val);
            for (int i = 0;i < size;i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->right) q.push(node->right);
                if (node->left) q.push(node->left);
            }
        }
        return ans;
    }
};

方法三：dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root,int depth,vector<int>& ans) {
        if (root == nullptr) return ;
        if (depth == ans.size()) ans.push_back(root->val);
        dfs(root->right,depth+1,ans);
        dfs(root->left,depth+1,ans);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        dfs(root,0,ans);
        return ans;
    }
};

题目链接：分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

方法一：动态规划+二维数组

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector dp(nums.size() + 1, vector<int> (2e4 + 10, 0));
        double sum = 0;
        for (auto x : nums) {
            sum += x;
        }
        double target = sum / 2;
        for (int i = 0;i < nums.size();i++) {
            for (int j = 0;j <= target;j++) {
                if (j < nums[i]) {
                    dp[i+1][j] = dp[i][j];
                }else 
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - nums[i]] + nums[i]);
            }
        }
        return dp[nums.size()][target] == target;
    }
};

方法二：动态规划+一维数组

//一维优化
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(2e4 + 10, 0);
        double sum = 0;
        for(int i = 0;i < nums.size(); ++i)
            sum += nums[i];
        double target = double(sum / 2);

        for(int i = 0; i < nums.size(); ++i)
            for(int j = target;j >= nums[i]; --j)
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        
        return dp[target] == target;
    }
};