详细线性DP题解
2024-11-16 21:23:39
发布于:浙江
24阅读
0回复
0点赞
我们先看题目,发现这道题是道明显的动态规划题目。
我们先看思路:
问题背景
假设我们有一个m x n的网格,我们需要计算从左上角(1, 1)到右下角(m, n)的所有可能路径数。每次移动只能向右或向下。
动态规划解法
我们可以使用动态规划来解决这个问题。动态规划的核心思想是将大问题分解为小问题,并利用小问题的解来构建大问题的解。
状态定义
我们定义dp[i][j]为从起点(1, 1)到(i, j)的路径数。
状态转移方程
根据题意,到达(i, j)的路径数可以由以下两种情况得到:
1.从(i-1, j)向下移动一步到达(i, j)。
2.从(i, j-1)向右移动一步到达(i, j)。
初始化*重点
为了正确计算路径数,我们需要初始化第一行和第一列
1.对于第一行(即j=1的情况),到达任意点(i, 1)的唯一路径都是来自上边的点(i-1, 1),因此第一行的所有点都应该初始化为1。
2.对于第一列(即i=1的情况),到达任意点(1, j)的唯一路径都是来自左边的点(1, j-1),因此第一列的所有点也应该初始化为1。
重点:状态转移方程
dp[i][j] = dp[i-1][j] + dp[i][j-1]
题解:
#include<iostream>
using namespace std;
long long dp[1001][1001];
int main(){
long long a,b;
cin>>a>>b;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
dp[1][j]=1;
dp[i][1]=1;
}
}
for(int i=2;i<=a;i++){
for(int j=2;j<=b;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[a][b]<<endl;
return 0;
}
给个赞吧!
全部评论 1
给个赞吧
2024-08-17 来自 浙江
0
有帮助,赞一个