德州极速网站建设小程序,seo优化培训学校,怎么做网站源码,wordpress发帖提示升级vip动态规划
思路#xff1a; 定义 dp[r][c] 为到达坐标 (r, c) 的路径数#xff1a; 它只能有同一行左边相邻方格向右到达或者同一列上方相邻方格向下到达#xff1b;状态转移方程#xff1a; dp[r][c] dp[r][c - 1] dp[r - 1][c]初始状态 dp[0][0] 1第一行的路径数是 1第…动态规划
思路 定义 dp[r][c] 为到达坐标 (r, c) 的路径数 它只能有同一行左边相邻方格向右到达或者同一列上方相邻方格向下到达状态转移方程 dp[r][c] dp[r][c - 1] dp[r - 1][c]初始状态 dp[0][0] 1第一行的路径数是 1第一列的路径数是 1动态规划求出所有 dp 数组的路径数结果为 dp[m - 1][n - 1]
class Solution {
public:int uniquePaths(int m, int n) {if (m 0 || n 0) {return 1;}std::vectorstd::vectorint dp(m, std::vectorint(n));dp[0][0] 1;for (int c 1; c n; c) {dp[0][c] 1;}for (int r 1; r m; r) {dp[r][0] 1;}for (int r 1; r m; r) {for (int c 1; c n; c) {dp[r][c] dp[r - 1][c] dp[r][c - 1];}}return dp[m - 1][n - 1];}
};
——————————————————————————————————
