LeetCode 动态规划 代码随想录笔记

class Solution {
public:

    int fib(int n) {
        if(n==0||n==1) return n;
        else return  fib(n-1)+fib(n-2);
    }
};

DP

class Solution {
public:

    int fib(int n) {
        if(n==0||n==1) return n;

        int dp[2];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;++i)
        {
            int sum=dp[0]+dp[1];
            dp[0]=dp[1];
            dp[1]=sum;

        }

        return dp[1];
    }
};

如果理解dp[0] dp[1]的取值过程有问题，在纸上画一画就行了。

class Solution {
public:
    int climbStairs(int n) {
        if(n==1||n==2) return n;
        int dp1=1,dp2=2;
        int sum;
        for(int i=3;i<=n;++i)
        {
            sum=dp1+dp2;
            dp1=dp2;
            dp2=sum;
        }
        return dp2;
    }
};

1. 第一步不花费体力，构建一个多余层，类似vector的end()的感觉，原本的下标 0-size()-1，现在0-size()

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
       
        vector dp(cost.size()+1);
        dp[0]=0;
        dp[1]=0;

        for(int i=2;i<=cost.size();++i)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[cost.size()];
    }
};

2. 第一步花费体力，每经过（“踏上”）一个台阶付出一定代价。

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n=cost.size();
        if(n==1) return cost[0];
        if(n==2) return min(cost[0],cost[1]);

        vector dp(cost.size());
        dp[0]=cost[0];
        dp[1]=cost[1];

        for(int i=2;i

class Solution {
public:
    int path(int i,int j)
    {
        if(i==0||j==0) return 1;
        else 
        {
            return path(i-1,j)+path(i,j-1);
        }
    }
    int uniquePaths(int m, int n) {
        int i=m-1,j=n-1;
        return path(i,j);
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector row(n,0);
        vector> path;
        for(int i=0;i