class Solution{public: int Fibonacci(int n)
{        // 初始值 
	if (n <= 0)
	{ 
		return 0; 
	} 
	if (n == 1 || n == 2) 
	{
		return 1; 
	}        
	// F(n)=F(n-1)+F(n-2) 
	return Fibonacci(n - 2) + Fibonacci(n - 1); }};

class Solution {
public:
    int Fibonacci(int n) {
        if(n==1 || n==2)
            return 1;
        int fn;
        int fn1 = 1, fn2 = 1;
        for(int i = 2; i < n; i++)
        {
            fn = fn1 + fn2;
            fn1 = fn2;
            fn2 = fn;
        }
        
        return fn;
        /*上述解法的空間復(fù)雜度為O(n)
        其實F(n)只與它相鄰的前兩項有關(guān)，
        所以沒有必要保存所有子問題的解
        只需要保存兩個子問題的解就可以
        下面方法的空間復(fù)雜度將為O(1)*/
        if(n==1 || n==2)
            return 1;
        int* F = new int[n];
        //初始狀態(tài)
        F[0] = 1;
        F[1] = 1;
        for(int i = 2; i < n; i++)
        {
            F[i] = F[i-1] + F[i-2];
        }
        
        return F[n-1];
    }
};

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.size();
        vector<bool> F(len+1, false);
        F[0] = true;
        for(int i = 1; i <= len; i++)
        {
            //F[8]的狀態(tài)：7<8 && F[7] && [8,8]
            //F[8]的狀態(tài)：6<8 && F[6] && [7,8] 
            for(int j = i-1; j >= 0; j--)
            {
                if(F[j] && dict.find(s.substr(j,i-j)) != dict.end())
                {
                    F[i] = true;
                    break;
                }
            }
        }
        
        return F[len];
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty())
            return 0;
        int row = triangle.size();
        vector<vector<int> > minSum(triangle);
        for(int i = 1; i < row; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                if(j == 0)
                    minSum[i][j] = minSum[i-1][j] + triangle[i][j];
                else if(j == i)
                    minSum[i][j] = minSum[i-1][j-1] + triangle[i][j];
                else
                    minSum[i][j] = min(minSum[i-1][j], minSum[i-1][j-1])
                                   + triangle[i][j];
            }
        }
        int result = minSum[row-1][0];
        for(int i = 1; i < triangle.size(); i++)
        {
            result = min(result, minSum[row-1][i]);
        }
        
        return result;
    }
};

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        vector<vector<int> > ret(m, vector<int>(n,1));
        for(int i = 1; i < m; i++)
        {
            for(int j = 1; j < n; j++)
            {
                ret[i][j] = ret[i-1][j] + ret[i][j-1];
            }
        }
        
        return ret[m-1][n-1];
    }
};

class Solution {
public:
    /**
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& grid) {
        // write code here
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        int M = grid.size();
        int N = grid[0].size();
        vector<vector<int> > ret(M, vector<int>(N,0));
        ret[0][0] = grid[0][0];
        for(int i = 1; i < N; i++)
        {
            ret[0][i] = ret[0][i-1] + grid[0][i];
        }
        for(int i = 1; i < M; i++)
        {
            ret[i][0] = ret[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < M; i++)
        {
            for(int j = 1; j < N; j++)
            {
                ret[i][j] = min(ret[i-1][j],ret[i][j-1]) + grid[i][j];
            }
        }
        
        return ret[M-1][N-1];
    }
};