AOJ0611 - Silk Road (DP)

AOJ0611のSilk RoadをDPの練習として解いてみました．
また，この問題を解くにあたって以下のサイトを参考にしました．

• 動的計画法（ナップサック問題） - アルゴリズム講習会

• 動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング

コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX_D (1000)
#define MAX_C (1000)
 
int N, M;
int D[MAX_D], C[MAX_C];
// -1ならまだ調べていない
int dp[MAX_D + 1][MAX_C + 1];
 
int rec_dp(int now, int day);
 
int main()
{
  scanf("%d%d", &N, &M);
  memset(dp, -1, sizeof(dp)); // -1でメモ化テーブルを初期化
 
  for (int i = 0; i < N; i++) scanf("%d", &D[i]);
  for (int i = 0; i < M; i++) scanf("%d", &C[i]);
 
  printf("%d\n", rec_dp(0, 0));
 
  return (0);
}

// nowは現在地，dayは何日目かを表す
int rec_dp(int now, int day)
{
  if (dp[now][day] != -1){ // 一度調べていたら再利用
    return (dp[now][day]);
  }
   
  int res;
  if (now == N){ // 目的地に到着
    res = 0;
  }
  else if (N - now == M - day){ // 目的地に到着するためには進むしかない場合
    res = rec_dp(now + 1, day + 1) + (D[now] * C[day]);
  }
  else { // 進むか待機するか決められる場合
    res = min(rec_dp(now, day + 1), rec_dp(now + 1, day + 1) + (D[now] * C[day]));
  }
 
  dp[now][day] = res; // 結果を保存
 
  return (dp[now][day]);
}

提出したやつ

今回はメモ化再帰のDPで解きました．
またmemsetを初めて使ってみました．(31行目がdp[now][day] != 0でもいけそう)
単純な再帰に手を加えると計算効率がだいぶ上がるので，マスター出来るようにしたい．
また，漸化式を用いたDPも出来るようになりたい．(forだけで書けるので見た目もタイプ量も減りそう)
もっとこここうした方がいいよ，などあればコメント等に書いて頂ければ幸いです．

(この記事はictechの「Markdown超入門」を受け，Markdownで書かれています)