LeetCode Unique Paths 动态规划与大数

A robot is located at the top-left corner of a?m?x?n?grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:?m?and?n?will be at most 100.

由于只能往下或者往右走，因此(i,j)只会由(i - 1,j)或者(i,j - 1)到达。

假设，到达(i - 1,j)有f[i - 1,j]种走法，到达(i,j - 1)有f[i,j - 1]种走法，那么到达(i,j)有f[i,j] = f[i - 1,j] + f[i,j - 1]中走法。

/*
 * kl.cpp
 *
 *  Created on: 2014年12月27日
 *      Author: judyge
 */

#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<time.h>
#include<windows.h>

#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4

using namespace std;

class BigNum
 {

 private:
     int a[500];    //可以控制大数的位数
     int len;       //大数长度
 public:
     BigNum(){ len = 1;memset(a,sizeof(a)); }   //构造函数
     BigNum(const int);
     friend ostream& operator<<(ostream&,BigNum&);
     BigNum operator+(const BigNum &) const;
     void print();
 };

 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
 {
     int c,d = b;
     len = 0;
     memset(a,sizeof(a));
     while(d > MAXN)
     {
         c = d - (d / (MAXN + 1)) * (MAXN + 1);
         d = d / (MAXN + 1);
         a[len++] = c;
     }
     a[len++] = d;
 }

 ostream& operator<<(ostream& out,BigNum& b)   //重载输出运算符
 {
     int i;
     cout << b.a[b.len - 1];
     for(i = b.len - 2 ; i >= 0 ; i--)
     {
         cout.width(DLEN);
         cout.fill('0');
         cout << b.a[i];
     }
     return out;
 }

 BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
 {
     BigNum t(*this);
     int i,big;      //位数
     big = T.len > len ? T.len : len;
     for(i = 0 ; i < big ; i++)
     {
         t.a[i] +=T.a[i];
         if(t.a[i] > MAXN)
         {
             t.a[i + 1]++;
             t.a[i] -=MAXN+1;
         }
     }
     if(t.a[big] != 0)
         t.len = big + 1;
     else
         t.len = big;
     return t;
 }

 void BigNum::print()    //输出大数
 {
     int i;
     cout << a[len - 1];
     for(i = len - 2 ; i >= 0 ; i--)
     {
         cout.width(DLEN);
         cout.fill('0');
         cout << a[i];
     }
     cout << endl;
 }


BigNum uniquePaths(int m,int n) {
        vector<vector<BigNum> > v(m,vector<BigNum>(n,1));
        for(int i=1; i<m; ++i){
            for(int j=1; j<n; ++j){
                v[i][j]=v[i-1][j]+v[i][j-1];
            }
        }
        return v[m-1][n-1];
    }





 int main(){



clock_t start,finish;
double time;
start=clock();


uniquePaths(1000,500).print();


finish=clock();
time=(double)((finish-start)/CLOCKS_PER_SEC);
printf("start:%ldttfinish:%ldtfinish-start:%ldtruntime:%fn",start,finish,finish-start,time);
return 0;

 }

21794643772475632607161961769677171260214971666986831475298702747021969894224312122274198675876219732944354758456178809790971668241976102754811035273030233861576123498221326050261052311668799203434574640707827487765370771640762604652965442259548989227841052691939812694812193778630470756833909910697283456008280175193445777429087108659795300989641974873048618112352532398954469345334076036542958624176451332960000
start:10		finish:1505	finish-start:1495	runtime:1.000000