algorithm - 動的計画法アルゴリズム

Question

私はスキルを向上させるためにいくつかのアルゴリズムを解決しようとしてこの教科書を読んでいますが、現在この問題で立ち往生しています:

この章は動的プログラミングに関するものであり、これらのタイプの問題にアプローチする方法がわからないため、問題を開始するのに本当に苦労しています。誰かがそれを解決するのを手伝ったり、似たような既存のアルゴリズムを教えてくれますか?

Answer 1

この問題の解決策は、次の再帰式の解決策です。

f(i) = max{ l_i + f(i+k_i) , f(i+1) }
f(x) = 0 : for all x > n

問題の解決策は、 の解決策ですf(1)。

説明: 毎日、この日を「スキップ」して次の日 (またはその次の日、...、これは を呼び出すことによって行われますf(i+1)) を確認するか、キャンディーを飲むことができます。日後にのみ戻るk_i-つまり、のソリューションを追加しますf(i+k_i)。