leetcode 动规规划（基础版）最小路径和

题目：

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

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

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

题解：

移动到每一个小整体的右下角的最小路径和是从它左边一个格子和右边一个格子值中选择一个最小的值再加上它自己本身的值。

int minPathSum(vector<vector<int>>& grid) {int dp[205][205]={0};dp[0][0]=grid[0][0];for(int i=1;i<grid[0].size();i++)dp[0][i]=dp[0][i-1]+grid[0][i];for(int i=1;i<grid.size();i++)dp[i][0]=dp[i-1][0]+grid[i][0];for(int i=1;i<grid.size();i++){for(int j=1;j<grid[0].size();j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}return dp[grid.size()-1][grid[0].size()-1];}

题后反思：

这道题其实思路很简单，但是还是费了点时间，因为动态规划是递推的升级版，是根据已有的推出新的，所以在作动态规划时要注意初始值的设置，特殊位置需要单独赋值。