動的計画法

const int h = 5, w = 4;

int dfs(int nowh, int noww){
    if(nowh > h || noww > w) return 0;
    if(nowh == h && noww == w) return 1;
    return dfs(nowh + 1, noww) + dfs(nowh, noww + 1);
}

const int h = 5, w = 4;
int dp[h + 1, w + 1];

int dfs(int nowh, int noww){
    if (nowh > h || noww > w) return 0;
    if (nowh == h && noww == w) return 1;
    if (dp[nowh][noww] != 0) return dp[nowh][noww];
    return dp[nowh][noww] = dfs(nowh + 1, noww) + def(nowh, noww + 1);
}

const int h = 5, w = 4;
int dp[h + 1][w + 1];

void calc(){
    int i, j;
    dp[0][0] = 1;
    for(i=0; i<=h; i++) {
        for(j = 0; j<= w; j++){
            if (i != 0) dp[i][j] += dp[i - 1][j];
            if (j != 0) dp[i][j] += dp[i][j - 1];
        }
    }
}

int ws[5] = {3, 4, 1, 2, 3};
int ps[5] = {2, 3, 2, 3, 5};
int maxw = 10;

int ret = 0;

void knapsack(int n, int w, int p){
    if ( w > maxw) return;
    ret = max(ret, p);
    if(n >= 5) return;
    knapsack(n + 1, w, p);
    knapsack(n + 1, w + ws[n], p + ps[n]);
}

int ws[5] = {3, 4, 1, 2, 3};
int ps[5] = {2, 3, 2, 3, 5};
int maxw = 10;
int dp[6][11];
int ret = 0;

for(int i = 0; i <= 5; i++){
    for(int j = 0; j <= maxw; j++) {
        if(j + ws[i] <= maxw){
            dp[i + 1][j + ws[i]] =
                max(dp[i + 1][j + ws[i]], dp[i][j] + ps[i]);
                ret = max(dp[i + 1][j + ws[i]], ret);
        }
    }
}