动态规划

不同路径

不同路径
这题其实并没有很难，在昨天刷了几道基础dp题之后，很快就做出来了，只不过中间有个初始化要小心一下。不过这道题最应该收获的，应该是其他两种做法。

1.DP解法

int dp[101][101]={0}; //dp数组表示到达dp[i][j]，即从起点到（i，j）有多少路径
       //第二步:状态转移方程:dp[i][j]=dp[i-1][j]+dp[i][j-1] ,因为(i,j)这个位置只能由上面和左边得到
       //第三步：初始化,dp[1][1]=0,dp[2][1]=1,dp[1][2]=1(错误的理解)
       //第四步：确定遍历顺序，因为dp[i][j]是由前面两个状态得到的，所以是顺序遍历
       for(int j=1;j<=n;j++)
       {
           dp[1][j]=1;
       }
       for(int i=1;i<=m;i++)
       {
           dp[i][1]=1;
       }
       for(int i=2;i<=m;i++)
       {
           for(int j=2;j<=n;j++)
           {
                  dp[i][j]=dp[i-1][j]+dp[i][j-1];
           }
       }
      return dp[m][n];

2.DFS（会超时）

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

3.数论的方法

这里就偷下懒，不自己写了，直接截了Carl的图

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;
    }
};

不同路径II

不同路径II

这道题和之前那道题相比多了障碍物的存在，只要在代码中特判一下就行了。

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

整数拆分

整数拆分

这道题属于最近做过最难的一道dp了，因为很难找出状态转移方程。

具体讲解链接：

DP的思路：拆解成两个数或者多个数。

//第一步：dp数组表示分解n可以得到的最大乘积
      int dp[60]={0};
      //第二步：状态转移方程：dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
      //第三步: 初始化dp[2]=1;
      //第四步：确定遍历顺序 因为dp[i]是由dp[j-i]得到的，所以是顺序遍历
      dp[2]=1;
      for(int i=3;i<=n;i++)
      {
          for(int j=1;j<i;j++)
          {
            dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
          }
      }
     return dp[n];
    }

其实这道题也可以用贪心来做，因为尽可能多份出来3可以保证最后的乘积最大，具体为什么要数学证明。

//贪心的方法:每次尽可能的分解成3，可以保证最后的乘积最大，不过需要数学证明
    int res=1;
    if(n==1) return 1;
    if(n==2) return 1;
    if(n==3) return 2;
    if(n==4) return 4;
    while(n>4)
    {
        res*=3;
        n-=3;
    }
    res*=n;
    return res;

今日复习代码

1.Acwing 785 快速排序 (1x)
2.Acwing 786 第K个数（1x)
3.Acwing 787 归并排序(1x)
4.Acwing 788 逆序对的数量(1x)