Clear c++ dynamic programming


  • 0
    H

    class Solution {

    public:

    int rob(vector<int>& nums) {
        int result;
        if(nums.empty()){
            return 0;
        }
        int n=nums.size();
        int **dp=new int*[n];
        for(int i=0;i<n;i++){
            dp[i]=new int[n];
        }
        for(int i=0;i<n;i++){
            dp[i][i]=nums[i];
        }
        for(int j=1;j<n;j++){
            for(int i=j-1;i>=0;i--){
                int s1=dp[i+1][j];
                int s2=dp[i][j-1];
                int s3=0;
                int s4=0;
                if(i<=j-2){
                    s3=dp[i][j-2]+nums[j];
                }
                dp[i][j]=max3(s1,s2,s3);
            }
        }
        return dp[0][n-1];
    }
    

    private:

    int max3(int a,int b,int c){
        int max1=a>b?a:b;
        max1=max1>c?max1:c;
        return max1;
    }
    

    };


Log in to reply
 

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