动态规划

学习动态规划思想后的学习总结，以便日后复习使用。

动态规划思想三要素：最优子结构、边界、状态转移公式。

  • 最优子结构
    要解决当前问题，需解决的简化后的子问题。
  • 边界
    问题结束的条件。
  • 状态转移公式
    联系当前子结构和上一级结构之间的表达式。

找寻上述三个要素的过程称为“建模”，其难点在于如何建立状态转移公式。

还是以几个问题为例对这一思想进行阐述吧。

斐波那契数列

指这样一个数列，第一项和第二项为1，其余项的值为它前两项值得和：1,1,2,3,5,8……n
问题：求第n项的值。

对于这个问题，最先想到的办法应该是通过递归解决，因为它的代码书写比较简单。

1
2
3
4
5
6
7
int fibo(vector<int> nums, int n)   
{   
    if(n <= 1){   
    return 1;   
    }   
    return fibo(nums, n - 1) + fibo(nums, n - 2);   
}

使用递归解决时，最大的问题就是进行了太多次无意义的重复函数调用，比如，在求n-1项和n-2项的值时，都调用了函数来求n-3项的值。具体有多少个重复项，可以自己画个二叉树来分析一下。
怎么避免呢？可以从以空间换时间的角度来思考一下，比如将所有已求得的值保存到哈希表中，当需要某项的值时，先从哈希表中查找，没有查找到时再递归运算。

在上面这一优化策略中就体现出了动态规划的思想：动态规划在于避免进行重复的运算，根据从低至上的策略，让先解决的子问题的结果作为后续问题的条件以避免重复求解相同的问题。

因此，我们可以这样来解决上述问题 

1
2
3
4
5
6
7
8
9
10
11
12
int fibo(vector<int> nums, int n)   
{   
    if(n <= 1){   
        return 1;   
    }   
    int f = 1, s = 1;   
    for(int i = 2; i < n; ++i){   
	    s = f + s;   
	    f = s - f;   
    }   
    return s;   
}

在上面的代码中，首先我们将s赋值为f+s；然后在通过s-f将f赋值为之前s的值；最终的s就是第n项的值

未完待续。。。


 上一页

 评论