题目给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足  j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。请你返回从 start 到 finish 所有可能路径的数目。由于答案可能很大， 请将它对 10^9 + 7 取余后返回。示例 1：输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5 输出：4 解释：以下为所有可能路径，每一条都用了 5 单位的汽油： 1 -> 3 1 -> 2 -> 3 1 ->

题目给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。思路定义dp[i][j]表示从左上角到位置(i,j)的路径上的最小数字总和。那么答案就是dp[m-][n-1]。状态转移方程为：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。i==0,dpi = dpi+gridi,j = 0,dpi = dpi-1+gridi。本题可以直接使用grid作为dp数组。代码如下代码class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); for(int i = 0;i < m;i++) { for(int j = 0;j < n;j++) {

题目一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。思路定义dp[i][j]表示从起点到位置(i,j)的不同路径。当obstacle[i][j]==1时，dp[i][j]=0。当obstacle[i][j]==0时，状态转移方程是dp[i][j] = dp[i-1][j]+dp[i][j-1]。直接使用滚动数组优化后的代码。代码class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<int> dp(n); dp[0] = (obstacl

题目一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？思路定义dp[i][j]表示从起点到点(i,j)的不同路径，则答案为dp[m-1][n-1]。i==0或者j==0,dp[i][j]=1;dp[i][j] = dp[i-1][j]+dp[i][j-1]，计算顺序为i从0到m、j从0到n代码class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m,vector<int>(n,1)); for(int i = 1;i < m;i++) { for(int j = 1;j < n;j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][

题目公司A有n个员工，数组happy表示n个员工产生快乐的分数，二维数组children表示公司的组织架构，children[i,j]=1代表i是j的直属上司。人事部门要举行一个聚会，为使聚会有愉悦的气氛，员工和其直属上司不会同时参加。请问怎么安排聚会名单，使聚会的快乐分数总和最大。输入:happy=[3,7,1,4,6,8,9,10,5,4,2,12,3,6] children=[[0,1,1,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,1,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,1,1,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0