6.动态规划

LeetCode.509.斐波那契数

class Solution {
public:
    int fib(int n) {
        int f[31];
        f[0] = 0;
        f[1] = 1;
        for(int i = 2;i < 31;i++){
            f[i] = f[i-1]+f[i-2];
        }
        return f[n];
    }
};

LeetCode.70.爬楼梯

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

LeetCode.746.最小代价爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        cost.push_back(0);
        int f[1005];
        f[0] = cost[0];
        f[1] = cost[1];
        for(int i = 2;i < cost.size();i++){
            f[i] = min(f[i-1],f[i-2])+cost[i];
        }
        return f[cost.size()-1];
    }
};

LeetCode.62.不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105][105];
        for(int i = 0;i < 105;i++){
            dp[i][0] = 1;
            dp[0][i] = 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];
    }
};

LeetCode.63.不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int dp[105][105];
        for(int i = 0;i < m;i++){
            if(obstacleGrid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }
        for(int i = 0;i < n;i++){
            if(obstacleGrid[0][i] == 1){
                break;
            }
            dp[0][i] = 1;
        }
        for(int i = 1; i < m;i++){
            for(int j = 1;j < n;j++){
                if(obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

LeetCode.343.整数拆分

class Solution {
public:
    int integerBreak(int n) {
        int dp[60];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 2;i <= n;i++){
            for(int j = 1;j <= i-1;j++){
                dp[i] = max(dp[i-j]*dp[j],dp[i]);
                dp[i] = max(dp[i-j]*j,dp[i]);
            }
        }
        dp[2] = 1;
        dp[3] = 2;
        return dp[n];
    }
};

LeetCode.96.不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n+1,0);
        G[0]=1;
        G[1]=1;
        for(int i = 2;i <= n;i++){
            for(int j = 1;j <= i;j++){
                G[i] += G[j-1] * G[i-j];
            }
        }
        return G[n];
    }
};