如何建立免费公司网站,舞蹈培训东莞网站建设,wordpress用户上传视频,做手机网站的公司一:题目 二:上码
class Solution {
public:/**思路:1.分析题意:2.动态规划五步走:1:确定dp数组和其下标的含义dp[i][j]为到达二维数组下标为i#xff0c;j的路径条数,i和j为下标2:确定dp数组的递推公式那么dp[i][j]是如何求解出来的呢?只能是两个方向左边:dp[i-1][j…一:题目 二:上码
class Solution {
public:/**思路:1.分析题意:2.动态规划五步走:1:确定dp数组和其下标的含义dp[i][j]为到达二维数组下标为ij的路径条数,i和j为下标2:确定dp数组的递推公式那么dp[i][j]是如何求解出来的呢?只能是两个方向左边:dp[i-1][j]上边:dp[i][j-1]那么dp[i-1][j]代表的是从坐标(0,0)点开始到dp[i-1][j]的路径条数dp[i][j-1]同理3:确定dp数组的初始化那么在二位数组范围内最上边一行和最左边一列都是1因为到这个路径均是1所以:for(int i 0; i n; i) {dp[0][i] 1;}for(int j 0; j m; j) {dp[j][0] 1;}4:确定dp数组的遍历顺序从左向右的遍历。5:举例验证dp数组m 3,n 7;1 1 1 1 1 1 11 2 3 4 5 6 71 3 6 10 15 21 28 */int uniquePaths(int m, int n) {int dp[m][n];for(int j 0; j n; j) {//列在变dp[0][j] 1;}for(int i 0; i m; i) {//行在变dp[i][0] 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][n-1];}
};
