算法修炼-动态规划之路径问题（1）

62. 不同路径 - 力扣（LeetCode）

        思路：选定一个网格为终点，走到这个网格的所有走法就是这个网格的上面一个网格的所有走法加上这个网格左边一个网格的所有走法，然后做好初始化工作就行。 

class Solution {
public:
       int uniquePaths(int m, int n) 
    {
        //dp表
        int arr[m][n];
 
        //特殊处理
        if(m == 1 || n == 1)
        return 1;
 
        //初始化
        for(int i = 0; i<m; i++)
        {
            arr[i][0] = 1;
        }
        for(int i = 0; i<n; i++)
        {
            arr[0][i] = 1;
        }
 
        //状态转移方程
        for(int i = 1; i<m; i++)
        {
            for(int j = 1; j<n; j++)
            {
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
        return arr[m-1][n-1];
    }
};

63. 不同路径 II - 力扣（LeetCode）

        思路： 这道题可以看做事上面那道题的升级版，我的思路就是先将创建出来的dp表先全部初始化为0，在状态转移方程中，如果遇到障碍物，就保持dp表中障碍物位置的值仍为0，其余位置的值为它的上面加上它的左边。这时有人可能就会有疑问了，如果一个位置的左边或者是上面为障碍物不影响赋值吗？答案是不影响的。因为障碍物位置的值就是0，加上跟没加没有区别，所以可以统一加上。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {   
 
        //dp表
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
 
        //初始化
        for(int i = 0; i<n; i++)
        {
            if(obstacleGrid[0][i] == 0)
            dp[0][i] = 1;
            else
            break;
        }
        for(int i = 0; i<m; i++)
        {
            if(obstacleGrid[i][0] == 0)
            dp[i][0] = 1;
            else
            break;
        }
        
 
        //状态转移方程
        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];

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

         思路：这题采用的方法略微跟上面两题不同，这一题的dp表我多补了一行和一列，通过比较所在位置的上面一个位置和左边一个位置谁大，加上值大的那个位置，只不过这种方法要注意两个表之间下标的对应关系。

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        //dp表
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
 
        //初始化+状态转移方程
        for(int i = 1; i<=m ;i++)
        {
            for(int j = 1; j<=n; j++)
            {
                if(dp[i-1][j] < dp[i][j-1])
                {
                    dp[i][j] += frame[i-1][j-1]+dp[i][j-1];
                }
                else
                {
                    dp[i][j] += frame[i-1][j-1] + dp[i-1][j];
                }
            }
        }
 
        return dp[m][n];
    }
};