LetCode 문제풀이 노트 62.서로 다른 경로[동적 기획]

10836 단어 Leetcode
동적 기획
토대
시간 복잡도: O(m∗n)O(m*n)O(m∗n)
공간 복잡도: O(m∗n) O(m*n) O(m∗n)
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<n;i++) dp[0][i]=1;
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
        return dp[m-1][n-1];           
    }
};
  • 최적화1: dp[i][j]=dp[i-1][j]+dp[i][j-1]로 인해 현재 줄과 이전 줄의 데이터(동적 방정식에서pre[j]=dp[i-1][j])를 보존하고 두 줄, 공간 복잡도 O(2n)만 보존하면 된다.
  • 최적화 2:cur[j]+=cur[j-1], 즉cur[j]=cur[j]+cur[j-1]는 사고방식 2–>cur[j]=pre[j]+cur[j-1]와 같기 때문에 공간 복잡도는 O(n)이다.

  • 최적화 1: 공간 복잡성 O(2n)
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<int> pre(n,1);
            vector<int> cur(n,1);
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++)
                    cur[j]=cur[j-1]+pre[j];
                pre=cur;
            }
            return pre[n-1];
        }
    };
    

    최적화 2: 공간 복잡성 O(n)
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<int> cur(n,1);
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++)
                    cur[j]+=cur[j-1];
            }
            return cur[n-1];
        }
    };
    

    좋은 웹페이지 즐겨찾기