LeetCode—DP

#1-70. Climbing Stairs

Solution1—Traversal:

class Solution {
public:
    int climbStairs(int n) {
        // f[i] = ClimbStairs(i);
        vector<int> f(n+1, 0);

        f[0] = 1;
        f[1] = 1;

        // f[i] = f[i-1] + f[i-2]
        for(int i = 2; i <= n; ++i){
            f[i] = f[i-1] + f[i-2];
        }

        return f[n];
    }
};

Solution2—Recursion:

class Solution {
public:
    int climbStairs(int n) {
        f_ = vector<int>(n+1, 0);
        return NumOfSolutions(n);
    }

private:
    int NumOfSolutions(int n){
        if(n <= 1) return 1;
        // without recording
        return NumOfSolutions(n-1) + NumOfSolutions(n-2);
    }
    vector<int> f_;
};

class Solution {
public:
    int climbStairs(int n) {
        f_ = vector<int>(n+1, 0);
        return NumOfSolutions(n);
    }

private:
    int NumOfSolutions(int n){
        if(n <= 1) return 1;
        // record the num that we have calculated
        if(f_[n] > 0) return f_[n];
        f_[n] = NumOfSolutions(n-1) + NumOfSolutions(n-2);
        return f_[n];
    }
    vector<int> f_;
};

Solution3—Binary Exponentiation:

Solution4—DP:

class Solution {
public:
    int climbStairs(int n) {
        int one = 1;
        int two = 1;
        int cur = 1;

        for(int i = 2; i <= n; i++){
            cur = one + two;
            two = one;
            one = cur;
        }

        return cur;
    }
};

Similar Problems:

#2-303. Range Sum Query - Immutable

Solution1—Directly:

class NumArray {
public:
    NumArray(vector<int>& nums) {
        // copy the vector
        nums_ = std::move(nums);
    }
    
    int sumRange(int left, int right) {
        int sum = 0;
        for(int k = left; k <= right; ++k){
            sum += nums_[k];
        }
        return sum;
    }

private:
    vector<int> nums_;
};

Solution2—Pretreatment:

class NumArray {
public:
    NumArray(vector<int>& nums) {
        // pretreatment
        int n = nums.size();
        if(n == 0) return;
        sums_ = vector<vector<int>>(n, vector<int>(n, 0));
        // sum every elem
        for(int i = 0; i < n; ++i){
            for(int j = i; j < n; ++j){
                for(int p = i; p <= j; ++p){
                    sums_[i][j] += nums[p];
                }
            }
        }
    }
    
    int sumRange(int left, int right) {
        return sums_[left][right];
    }

private:
    vector<int> nums_;
    vector<vector<int>> sums_;
};

Solution3—DP:

class NumArray {
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return;
        sums_ = vector<int>(n, 0);

        // DP
        // sums_[i]: nums[0] + nums[1] + ... + nums[i]
        // sums_[i] = sums_[i-1] + nums[i]; // i > 1
        sums_[0] = nums[0];
        for(int i = 1; i < n; ++i){
            sums_[i] = sums_[i - 1] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        if(left == 0) return sums_[right];
        return sums_[right] - sums_[left-1];
    }

private:
    vector<int> sums_;
};

Summary:

Similar Problems:

#3-62. Unique Paths

Solution1—DFS:

class Solution {
public:
    int uniquePaths(int m, int n) {
        // require you to cal how many path, that possiblly using the dp method
        // using the planing dp
        // time(2^n) -> n^2
        
        // if it is out of the range(m < 0, or the n < 0), than return 0
        // at the beginning, it return 1
        if(m < 0 || n < 0) return 0;
        if(m == 1 && n == 1) return 1;
        if(f_[m][n] > 0) return f_[m][n]; // it haved covered before
        int left_paths = uniquePaths(m-1, n);
        int top_paths = uniquePaths(m, n-1);
        f_[m][n] = left_paths + top_paths;
        return f_[m][n];
    }

private:
    // using the unordered_map to store 2D matrix
    unordered_map<int, unordered_map<int, int>> f_;
};

Solution2-DP:

class Solution {
public:
    int uniquePaths(int m, int n) {
        auto f = vector<vector<int>>(n+1, vector(m+1, 0));

        f[1][1] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(i == 1 && j == 1){
                    continue;
                }else{
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[n][m];
    }
};

#4-53. Maximum Subarray

Solution1—DP:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // using dp
        // f[i] // maxSubArray(0...i) // start from the index 0
        // f[i] = f[i-1] > 0 ? nums[i] + f[i-1] : nums[i]
        // if the elem is negative and we start again
        // [-2,1,-3,4,-1,2,1,-5,4]
        // [-2,1,-2,4, 3,5,6, 1,4]
        // using dp to solve the problems
        // using the formalu to make it
				// f is the maximum until now
        vector<int> f(nums.size());
        f[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i){
            // if the f[i] is < 0, then don't touch me!
            // dp form
            f[i] = max(nums[i] + f[i-1], nums[i]);
        }

        return *std::max_element(f.begin(), f.end());
    }
};

#5-1218. Longest Arithmetic Subsequence of Given Difference

Solution1—DP:

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> dp;

        int ans = -INT_MAX;
        
        for(const auto &elem: arr){
            dp[elem] = dp[elem - difference] + 1;
            ans = max(dp[elem], ans);
        }

        return ans;
    }
};

#6-1137. N-th Tribonacci Number

Solution1—DP:

class Solution {
public:
    int tribonacci(int n) {
        // dp
        int f_0 = 0;
        int f_1 = 1;
        int f_2 = 1;
        int f_n = -1;

        if(n == 0) return f_0;
        if(n == 1) return f_1;
        if(n == 2) return f_2;
        
        for(int i = 2; i < n; ++i){
            f_n = f_0 + f_1 + f_2;
            f_0 = f_1;
            f_1 = f_2;
            f_2 = f_n;
        }

        return f_n;
    }
};

#7-121. Best Time to Buy and Sell Stock

Solution1—DP

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // using the space to record the mini value that have cover 
        
        int min_price = INT_MAX;
        int max_earn = -INT_MAX;

        for(const auto &elem: prices){
            min_price = min(min_price, elem);
            max_earn = max(max_earn, elem - min_price);
        }

        return max_earn;
    }
};

Solution2-Reduce to LC.53