תודה רבה לך על המסמך :)
כן, באמת היה לי את העותק הלא עדכני, כנראה מהיום הראשון שזה פורסם….
זה עדיין לא ממש מתיישב לי, אבל אני מניח שבשביל זה יש את יום שני (בין השאר..). עד אז אנסה לעבור על זה שוב.
בכל מקרה, רציתי לשאול שאלה כללית על האלגוריתמים בתכנות דינאמי:
הגדרנו אלגוריתם של תכנות דינאמי כאלגוריתם שבו מחשבים תתי-בעיות קטנות יחסית, ולאט לאט בונים את התמונה הגדולה על סמך תתי הבעיות האלו.
בכל התרגילים שעשינו עד כה, תמיד התחלנו בתת-בעיה מסדר גודל של 1, או משהו בסגנון.
האם ייתכן מצב שבו תת הבעיה ה'קלה' לפתרון היא דווקא כאשר מתחילים מסדר גבוה?
למשל, האם יכול להיות שהערך:
C[n]
הוא קל יותר לחישוב מאשר
C[1]?
שדווקא חישוב הערך של
C[1]
הוא זה שיעזור בפתרון הבעיה?
המון המון תודה! :)