动态规划【ing】

509. 斐波那契数

  • 递归

    class Solution {
    public:
      int fib(int n) {
          if(n<2) return n;
          return fib(n-1)+fib(n-2);
      }
    };
  • 动态规划

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

70. 爬楼梯

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

746. 使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i=2; i<cost.size(); i++) {
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
        }
        // 结果取最后一个的计算 最后一个不需要加入本本身花费
        return min(dp[cost.size()-1], dp[cost.size()-2]);
    }
};

62. 不同路径

  • DFS超时写法

    class Solution {
    public:
      int backtracking(int m, int n, int curm, int curn) {
          if(curm==m && curn==n) return 1;
          if(curn>n || curm>m) return 0;
          return backtracking(m, n, curm+1, curn)+backtracking(m, n, curm, curn+1);
      }
      int uniquePaths(int m, int n) {
          return backtracking(m,n,1,1);
      }
    };
  • 动态规划

    class Solution {
    public:
      int uniquePaths(int m, int n) {
          vector> dp(m, vector(n, 0));
          // 初始化
          for(int i=0; i
  • 数论

    class Solution {
    public:
      int uniquePaths(int m, int n) {
          long long numerator = 1; // 分子
          int denominator = m - 1; // 分母
          int count = m - 1;
          int t = m + n - 2;
          while (count--) {
              numerator *= (t--);
              while (denominator != 0 && numerator % denominator == 0) {
                  numerator /= denominator;
                  denominator--;
              }
          }
          return numerator;
      }
    };

63. 不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n,0));
        for(int i=0; i<m && obstacleGrid[i][0]!=1; i++)  dp[i][0] = 1;
        for(int i=0; i<n && obstacleGrid[0][i]!=1; i++)  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]=0;
                } else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        return dp[m-1][n-1];
    }
};

343. 整数拆分

class Solution {
public:
    int integerBreak(int n) {
        if(n<3) return 1;
        vector<int> dp(n+1,0);
        dp[1] = 1;
        dp[2] = 1;
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++){
                // 分解成2个:i*(j-i),分解成多个:dp[i-j]*j
                // 取本身的原因:还要和本身比
                dp[i] = max(dp[i],max(j*(i-j),dp[i-j]*j));  
            }
        return dp[n];
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇