详细线性DP题解

我们先看题目，发现这道题是道明显的动态规划题目。
我们先看思路：
问题背景
假设我们有一个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;
}

给个赞吧！