fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. 	int t;
  7. 	cin>>t;
  8. 	while(t--)
  9.     {
  10. 		int n, m;
  11. 		cin>>n>>m;
  12.  
  13. 		int dp[2][m];
  14. 		for(int j = 0; j < m; j++)
  15.         {
  16. 			dp[0][j] = dp[1][j] = 1;
  17.         }
  18.  
  19. 		for(int i = 1; i < n; i++)
  20. 		{
  21. 			for(int j = 1; j < m; j++)
  22. 			{
  23. 			    // dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];
  24. 			    // i = 1 since 1 is the current row, so i-1 = 0
  25. 				dp[1][j] = dp[0][j] + dp[1][j-1] + dp[0][j-1];
  26. 			}
  27.  
  28. 			for(int j = 1; j < m; j++)
  29.             {
  30.             	// copying the 1th row to 0th row
  31.                 dp[0][j] = dp[1][j];
  32.             }
  33. 		}
  34.  
  35. 		cout<<dp[1][m-1]<<"\n";
  36. 	}
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
5
1 1
2 2
3 3
4 4
5 5
stdout 
1
3
13
63
321
https://ideone.com/P5KAC4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!