动态规划相关题目

CC31 三角形 题目 题解(4) 讨论(142) 排行 中等 通过率：27.90% 时间限制：1秒 空间限制：32M 知识点 动态规划 描述 给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字， 例如，给出的三角形如下： [[20],[30,40],[60,50,70],[40,10,80,30]] 最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。 注意： 如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。

public:
    int minimumTotal(vector<vector<int> > &triangle) { 
        int row = triangle.size();
        int col = triangle[0].size();
        for(int i = 1 ; i<row ;++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                if(j == 0)
                {
                    triangle[i][j] += triangle[i-1][j];
                }
                else if(j == i)
                {
                    triangle[i][j] += triangle[i-1][j -1];
                }
                else
                {
                    triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);
                }
            }
        }
        int MinNum = triangle[row - 1][0];
        for(int i = 1; i < row ; ++i)
            MinNum = min(MinNum,triangle[row -1][i]);
        return MinNum;
    }
};

第二中方法，自底向上，可以不用特殊处理

public:
    int minimumTotal(vector<vector<int> > &triangle) { 
        int row = triangle.size();
        int col = triangle[0].size();
        for(int i = row - 2; i>=0; --i)
        {
            for(int j = 0; j <= i; ++j)
            {
                  triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

链接CC88 不同路径的数目(一)

public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        vector<vector<int>>v (m,vector<int>(n,1));
        for(int i = 0; i< m; ++i)
            v[i][0] = 1;
        for(int i =0; i< n; ++i)
            v[0][i] = 1;
        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j< n; ++j)
            {
                v[i][j] = v[i-1][j] + v[i][j -1];
            }
        }
        return v[m -1][n-1];
    }
};

链接CC86 带权值的最小路径和

public:
    /**
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& grid) {
        int row = grid.size();
        int col = grid[0].size();
        for(int i = 1; i< col; ++i)
        grid[0][i] += grid[0][i-1];
        for(int j = 1; j < row ;++j)
        grid[j][0] += grid[j-1][0];
        
        for(int i = 1; i< row; ++i)
        {
            for(int j = 1; j< col; ++j)
            {
                grid[i][j] += min(grid[i][j -1],grid[i -1][j]);
            }
        }
        return grid[row -1][col -1];
    }
};