読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

ProjectEuler Problem15 : Lattice paths

問題リンク:Problem 15 - Project Euler

問題概要:
20*20のグリッドの左上からスタートして右か下のみに移動できる時、グリッドの右下へ到達できるルートはどのくらい存在するか

解法:
よくあるdp
i*jに到達できるルートはdp[i][j]:=dp[i][j-1]+dp[i-1][j]となる
iまたはjが0の時、dp[i][j]=0である

コード:

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
  unsigned long long dp[21][21];
  for(int i=0;i<21;i++)
    dp[i][0] = dp[0][i] = 1;

  for(int i=1;i<21;i++)
    for(int j=1;j<21;j++)
      dp[i][j] = dp[i-1][j] + dp[i][j-1];

  cout << dp[20][20] << endl;
  return 0;
}