70.Climbing Stairs

Description:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

1
2
3
4
5
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int climbStairs(int n) {
        int * dp = new int[n+1];
        dp[0] = 0;
        if (n == 1) {
            dp[1] = 1;
            return dp[1];
        }
        else if (n == 2) {
            dp[2] = 2;
            return dp[2];
        }
        else {
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    }
};

746.Min Cost Climbing Stairs

Description:

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

1
2
3
4
5
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector <int> dp(n+1);
        dp[0] = 0;
        if (n <= 1) {
            return 0;
        }
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
};

62. Unique Paths

Description:

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

img

1
2
Input: m = 3, n = 7
Output: 28

Example 2:

1
2
3
4
5
6
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniquePaths(int m, int n) {
        int grid[m][n];
        for (int i = 0; i < m; i++) {
            grid[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            grid[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = grid[i-1][j] + grid[i][j-1];
            }
        }
        return grid[m-1][n-1];
    }
};

*Number Theory

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};

Reference:

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.md

63. Unique Paths II

Description:

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

img

1
2
3
4
5
6
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

img

1
2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1.

Dode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid[0].size();     //column
        int n = obstacleGrid.size();        //raw
        int dp[n][m];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
                break;
            }
            else {
                dp[0][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
                break;
            }
            else {
                dp[i][0] = 1;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                }
                else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[n-1][m-1];
    }
};

343.Integer Break

Description:

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

1
2
3
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

1
2
3
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

  • 2 <= n <= 58

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 0; j <= i/2; j++) {
                dp[i] = max(dp[i], max(dp[j], j) * max(dp[i-j], i-j));
            }
        }
        return dp[n];
    }
};

96. Unique Binary Search Trees

Description:

Given an integer n, return *the number of structurally unique **BST’*s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

img

1
2
Input: n = 3
Output: 5

Example 2:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 19

Code:

Choose every number as the root for one time. Calculate right and left dividedly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        if (n == 0) return 0;
        dp[0] = 1;
        dp[1] = 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[i-j-1] * dp[j];
            }
        }
        return dp[n];
    };
};

416. Partition Equal Subset Sum(01背包问题)

Description

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

1
2
3
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        vector<vector<bool>> dp(n);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            dp[i].resize(sum+1);
        }
        for (int j = 0; j <= sum; j++) {
            if (j == nums[0]) {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= sum; j++) {
                if (j >= nums[i] && dp[i-1][j-nums[i]] == true) {
                    dp[i][j] = true;
                }
                else if (nums[i] == j || dp[i-1][j] == true) {
                    dp[i][j] = true;
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[n-1][sum];
    }
};

1049 Last Stone Weight II

Description:

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:

1
2
3
4
5
6
7
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

1
2
Input: stones = [31,26,33,21,40]
Output: 5

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int len = stones.size(), sum = 0;
        for (int i = 0; i < len; i++) {
            sum += stones[i];
        }
        vector<int> dp(1501, 0);
        int result = sum / 2;
        for (int i = 0; i < len; i++) {
            for (int j = result; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }
        return sum - dp[result] - dp[result];
    }
};

* 494 Target Sum

Description:

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

  • For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

1
2
Input: nums = [1], target = 1
Output: 1

Constraints:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

* 474. Ones and Zeroes

Description:

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

1
2
3
4
5
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

1
2
3
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits '0' and '1'.
  • 1 <= m, n <= 100

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
        for (auto str : strs) {
            int sum1 = 0, sum0 = 0;
            for (auto c : str) {
                if (c == '0')   sum0++;
                else    sum1++;
            }
            for (int i = m; i >= sum0; i--) {
                for (int j = n; j >= sum1; j--) {
                    dp[i][j] = max(dp[i][j], dp[i-sum0][j-sum1] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

518. Coin Change II

Description:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

1
2
3
4
5
6
7
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

1
2
3
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

1
2
Input: amount = 10, coins = [10]
Output: 1

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (auto i : coins) {
            for (int j = i; j <= amount; j++) {
                dp[j] += dp[j-i];
            }
        }
        return dp[amount];
    }
};

377. Combination Sum IV

Description:

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

1
2
Input: nums = [9], target = 3
Output: 0

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

322. Coin Change

Description:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

1
2
3
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

1
2
Input: coins = [2], amount = 3
Output: -1

Example 3:

1
2
Input: coins = [1], amount = 0
Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(10001, 0xffff);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i < coins[j]) continue;
                dp[i] = min(dp[i-coins[j]]+1, dp[i]);
            }
        }
        if (dp[amount] == 0xffff)   return -1;
        return dp[amount];
    }
};

279. Perfect Squares

Description:

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

1
2
3
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numSquares(int n) {
        vector<int> num;
        int cur = 1;
        while(cur*cur <= n) {
            num.push_back(cur*cur);
            cur++;
        }
        vector<int> dp(n+1, 0xffff);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < num.size(); j++) {
                if (i < num[j]) continue;
                dp[i] = min(dp[i-num[j]]+1, dp[i]);
            }
        }
        if (dp[n] == 0xffff)    return -1;
        return dp[n];
    }
};

* 139. Word Break

Description:

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

1
2
3
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1
2
3
4
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());        //先把vector类型转化为unordered_set类型！
        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++) {
                string word = s.substr(j, i-j);
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

* 198. House Robber

Desription:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

1
2
3
4
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Code:

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

* 213. House Robber II

Description:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

1
2
Input: nums = [1,2,3]
Output: 3

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp1(len, 0);
        if (len == 1)   return nums[0];
        //分三种情况，不考虑首尾、不考虑尾，不考虑首，后两者包含第一种情况
        int res1 = get_max(0, len-2, nums);
        int res2 = get_max(1, len-1, nums);
        return max(res1, res2);

    }
    int get_max(int start, int end, vector<int>& nums) {
        if (start == end)   return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start+1] = max(nums[start], nums[start+1]);
        for (int i = start+2; i <= end; i++) {
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
};

337. * House Robber III

Description:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

img

1
2
3
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

img

1
2
3
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 0 <= Node.val <= 104

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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:
    int rob(TreeNode* root) {
        vector<int> result = robtree(root);
        return max(result[0], result[1]);
    }

    vector<int> robtree(TreeNode* cur) {
        if (cur == nullptr) return vector<int>{0, 0};
        vector<int> left = robtree(cur->left);
        vector<int> right = robtree(cur->right);
        int val1 = cur->val + left[0] + right[0];
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

1035. Uncrossed Lines

Description:

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

  • nums1[i] == nums2[j], and
  • the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Example 1:

img

1
2
3
4
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:

1
2
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:

1
2
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

Constraints:

  • 1 <= nums1.length, nums2.length <= 500
  • 1 <= nums1[i], nums2[j] <= 2000

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i-1] == nums2[j-1])   dp[i][j] = dp[i-1][j-1] + 1;
                else    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};

53. Maximum Subarray

Description:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

1
2
3
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

1
2
3
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

1
2
3
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len+1, 0);
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            ans = max(dp[i], ans);
        }
        return ans;
    }
};

392. Is Subsequence

Description:

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

1
2
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

1
2
Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 104
  • s and t consist only of lowercase English letters.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int slen = s.length(), tlen = t.length();
        vector<vector<int>> dp(slen+1, vector<int>(tlen+1, 0));
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= tlen; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        if (dp[slen][tlen] == slen) {
            return true;
        }
        else {
            return false;
        }
    }
};

115. *Distinct Subsequences

Description:

Given two strings s and t, return the number of distinct

*subsequences*

of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

Example 2:

1
2
3
4
5
6
7
8
9
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag

Constraints:

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numDistinct(string s, string t) {
        int len1 = s.length(), len2 = t.length();
        vector<vector<uint64_t>> dp(len1+1, vector<uint64_t>(len2+1, 0));
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len2; i++) {
            dp[1][i] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
};

583. Delete Operation for Two Strings

Description:

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:

1
2
3
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

1
2
Input: word1 = "leetcode", word2 = "etco"
Output: 4

Constraints:

  • 1 <= word1.length, word2.length <= 500
  • word1 and word2 consist of only lowercase English letters.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<vector<uint64_t>> dp(len1+1, vector<uint64_t>(len2+1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1[i-1] == word2[j-1])   dp[i][j] = dp[i-1][j-1] + 1;
                else    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return len1 - dp[len1][len2] + len2 - dp[len1][len2];
    }
};

72. Edit Distance

Description:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Example 1:

1
2
3
4
5
6
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

1
2
3
4
5
6
7
8
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};

647. Palindromic Substrings

Description:

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

1
2
3
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length(), result = 0;
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        for (int i = len-1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        result++;
                    }
                    else if (dp[i+1][j-1] == true) {
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;
    }

};