C++,My solution,DP


  • 19
    C
    class Solution {
    public:
        int rob(vector<int>& nums) {
            const int n = nums.size();
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            if (n == 2) return max(nums[0], nums[1]);
            vector<int> f(n, 0);
            f[0] = nums[0];
            f[1] = max(nums[0], nums[1]);
            for (int i = 2; i < n; ++i)
                f[i] = max(f[i-2] + nums[i], f[i-1]);
            return f[n-1];
        }
    };

  • 0
    X

    Your solution looks good. But it might fail the test case below:
    2, 5, 17, 3, 9, 28, 19, 29, 5, 7, 31
    The expected result for this test case should be 2+17+28+29+31 = 107;
    But the result of your code will be 5+3+28+29+31 = 96;


  • 1
    C

    I have tested your case and the result is 107. :)


  • 0
    X

    Correct, my mistake.


  • 0
    X

    you can save some space by rotating your cache.

    class Solution {
    public:
        int rob(vector<int> &nums) {
            int n = nums.size();
            if (n == 0) {
                return 0;
            } else if (n == 1) {
                return nums[0];
            }
    
            int dp[2] = {nums[0], std::max(nums[0], nums[1])};
            for (int i = 2; i < n; ++i) {
                dp[i % 2] = std::max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2]);
            }
            return dp[(n - 1) % 2];
        }
    };
    

  • 0

    said in C++,My solution,DP:

    if (n == 2) return max(nums[0], nums[1]);

    Nice solution, This line is not needed : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.