动态规划跳跃问题c++

Question

（用动态规划，c++实现）
小明在数轴上的坐标 0 处。现在小明将进行N次跳跃。第i次朝数轴正方向跳ai或bi个单位。请你判断跳N次以后他能否停留在坐标X

输入描述

第一行输入N和X，接下来N行输入ai和bi，其中
1≤i≤N
1≤ai,bi≤100
1≤X≤10000

输出描述

如果能在 N 次跳跃后到达位置 X，则输出 Yes，否则输出 No。

用例输入

2 10
3 6
4 5

用例输出

Yes

Answer 1

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 10010;
int Num[MAX_N][2];

int Sum[MAX_N][MAX_N];
int N, X;
int main()
{
cin >> N >> X;
for (int i = 1; i <= N; i++)
{
cin >> Num[i][0] >> Num[i][1];
}
Sum[0][0] = 1;
for (int i = 1; i <= N; i++)
{
for (int j = 0; j <= X; j++)
{
if (Sum[i - 1][j])
{
Sum[i][j + Num[i][0]] = Sum[i][j + Num[i][1]] = 1;
}
}
}
if (Sum[N][X]==1)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}