120.三角形最小路径和(中等)

题目：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

将该三角形用二维数组表示

[
	[2],
	[3, 4],
	[6, 5, 7],
	[4, 1, 8, 33]
]

可以看出，想要知道最短路径就需要知道从顶到各层的最短路径。
也就是说从 [2] 第一层开始，第一层的最短路径为 2，接下来需要知道第二层 [3, 4] 的最小值，与第一层最短路径 2 相加，就是第二层结束之后的最短路径。
依次遍历下去。

但需要注意的是，题目规定每一步只能移动到下一行中相邻的结点上， 这就意味着只能向三角形的“左下”和“右下”方前进。

因此根据动态规划的步骤：

• 将问题划分为子问题来得到最优解
  需要求出的是从顶点到整体的最短路径，因此我们逐层来取得最短路径
• 我们设定状态转移方程, 使用二维数组dp来存储路径的和
  根据题目我们可以获得状态转移方程
  dp[i][j] = min( dp[i+1][j] , dp[i+1][j+1] ) + path[i][j]
• 判断边界条件，当到达三角形的底或者右边时结束

如果要从上到下来求解最短路径，除过判断边界条件，还要判断底的最小值才能求得最终的最短路径。因此从下到上求解该问题就会省去很多问题。

class Solution {
    
public:
    int minimumTotal(vector<vector<int>>& triangle) {
    
        if(triangle.empty()){
    
            return 0;
        }
        int row = triangle.size();          // row of the triangle
        int column = triangle.back().size();    // Size of the last row in the triangle
        vector<vector<int>> dp(row+1, vector<int>(column+1, 0));
        // Adding another row is designed to caculate the last row of dp. 
        for(int i = row - 1; i >= 0; --i){
    
            for(int j = 0; j < triangle[i].size(); j++){
    
                // state transition equation
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
};

64.最小路径和(中等)

题目：

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

典型的动态规划题。
首先根据题意，该网格由一个二维数组m×n构成，因此可以得到路径开始于左上角也就是二维数组的 [0][0] 位置，通过向右或者向下移动最终到达终点为 [m][n] 的点，现在要使得该路径的和最小，就要使用动态规划法。

根据动态规划的一般步骤：

• 分析问题和求得子问题； 我们将求得最终的最短路径定为最终问题，求得阶段的最短路径为子问题
• 边界条件；当遍历到二维数组的右边界和下边界，该求解过程结束
• 状态转移方程；从左上角开始到右下角
  dp[i][j] += min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
• 求解

不过当我们使用dp数组来存储最短路径结果时会发现，当i = 0, j = 0，时会存在边界问题。观察可知第一行只能向右前进，第一列只能向下前进， 因此我们将第一行和第一列提前算出结果，此时就不用考虑边界情况。

当循环结束时，返回dp[m][n] ， 就是最短路径。

class Solution {
    
public:
    int minPathSum(vector<vector<int>>& grid) {
    
        if(grid.empty()){
    
            return 0;
        }
        int row = grid.size();      
        int column = grid.back().size();
        vector<vector<int>> dp(row, vector<int>(column, 0));
        dp[0][0] = grid[0][0];
        for(int i = 1; i < row; i++){
           // Caculate result of the first column
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1; j < column; j++){
        // Caculate result of the first row
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for(int i = 1; i < row; i++){
    
            for(int j = 1; j < column; j++){
    
                // state transition equation
                dp[i][j] += min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
};

198.打家劫舍(简单)

题目：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

一道非常经典的动态规划题目。
根据题意来简化该题目，遍历数组时不能对连续的两个数字求和，最后获得在不违反该条件下可以得到的最大数字之和。

根据动态规划的一般步骤：

• 分析问题，划分子问题；求得最终的数字之和为最后结果，求得阶段性的最大数字之和为子问题
• 边界条件；不能对连续的两个数字求和，当遍历结束或者没有下一个可以相加的数字结束
• 状态转移方程；
  要得到目前的最大数字和，需要知道目前的数字与之前的第二个数字的和，将此数字之和与此前第一个数字和比较，取最大一个就是目前的最大数字和。
  dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
• 遍历结束

要使得该状态方程可以运行，必须从数字i = 2开始，因此为了不必要的麻烦，将dp的数组长度在nums的长度上加一，将**dp[0]**设置为0，dp[1]设置为nums[0] 。

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        if(!nums.size()){
    
            return 0;
        }
        if(nums.size() == 1){
    
            return nums[0];
        }
        int len = nums.size();
        vector<int> dp(len+1, 0);		// len + 1
        dp[0] = 0, dp[1] = nums[0];		// Initialization
        for(int i = 2; i <= len; i++){
    
        	// state transition equation
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]) ;
        }

        return dp[len];
    }
};

62.不同路径(中等)

题目：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

输入: m = 7, n = 3
输出: 28

同与最小路径和一样的解题步骤，只是对dp的初始化和状态转移方程稍加修改。

按照动态规划的解题步骤：

• 分析问题，将问题划分为子问题；要求从点(0,0)得到的点(m-1,n-1) 的所有路径和，就要知道从(0,0)到(0,1), (1,0) …… 的路径和，再将路径和相加就是到点(m-1, n-1)的路径和
• 边界条件；初始化第一行和第一列，到达数组边界结束
• 状态转移方程；不难看出，机器人智能向右向下移动，因此参考最小路径和可得状态转移方程
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 遍历结束

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        if(!m || !n){
    
            return 1;
        }
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++){
         // Initialization of the first column
            dp[i][0] = 1; 
        }
        for(int j = 0; j < n; j++){
         // Initialization of the first row
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++){
    
            for(int j = 1; j < n; j++){
    
                // state transition equation
                dp[i][j] += dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};