leetcode 초급 알고리즘 동적 기획

동적 기획

계단 오르기

주식을 매매하기에 가장 좋은 시기

최대 하위 시퀀스 및

가재도구

계단을 오르다
사고방식: n=1, 한 걸음만 갈 수 있다.n=2, 두 가지 방법.n=3, 한 걸음, 두 걸음.n=4, 상위 AC 코드:

class Solution {
public:
    int climbStairs(int n) {
        int methods[n+1];
        if(n==1) return 1;
        if(n==2) return 2;
        methods [1] = 1;
        methods[2] = 2;
        for(int i =3;i<=n;i++)
        {
            methods[i] = methods[i-1]+methods[i-2];
        }
        return methods[n];
    }
};

주식을 매매하기에 가장 좋은 시기
AC 코드:

class Solution {
public:
    int maxProfit(vector& prices) {
        int len = prices.size();
        if(len==0) return 0;
        int profit[len];
        profit[0] = 0;
        for(int i =1;imaxPro)
                    maxPro = prices[i]-prices[j];
            }
            profit[i] = maxPro>profit[i-1]?maxPro:profit[i-1];
        }
        return profit[len-1];
    }
};

최대 하위 및
집을 약탈하다
AC 코드:

class Solution {
public:
    int rob(vector& nums) {
        int len = nums.size();
        if(len==0) return 0;
        int vis[len],notvis[len];
        vis[0] = nums[0];
        notvis[0] = 0;
        for(int i = 1;ivis[i-1]?notvis[i-1]:vis[i-1];
            vis[i] = notvis[i-1]+nums[i];
        }
        return notvis[len-1]>vis[len-1]?notvis[len-1]:vis[len-1];
    }
};