异想天开

What's the true meaning of light, Could you tell me why

动态规划

日期:2013-10-14 12:20:33
  
最后更新日期:2015-07-16 10:00:15
目录:
1.简介
2.题目一
3.题目二

一.动态规划
动态规划,经典的说法是将大问题分解为小问题,换一种说法,动态规划是用一系列的子问题去求解一个大问题。前者是递归版本,后者是迭代版本。所以动态规划的关键是子问题的划分。动态规划,我的理解是:
1.对于计算过程大量重复的时候,应该有一种直觉敏感,这个计算结果可以通过动态规划的得到的;
2.有时候换一种说法,将问题等价转化,或得到更通用的形式,或得到你更容易理解的形式(因为他人的表达方式对于你而言,可能很拗口);
3.采取执果索因的形式,我要得到什么最后的结论,所以我需要什么中间结论,这个过程中,你可以定义一个函数帮助你求解;
4.对于解题过程中,当你感到不痛快的时候,应该停止解题,或者换一种简单的办法,我比较接受博客网站betterexplained的博主的说法,“学习而言,一次痛苦的经验,会毁掉你之前所有美好的体验”,我觉得长期下去,这样的经验会让你觉得学习本身就是一件痛苦的事,所以这个时候你应该停下来了;
5.对于动态规划,解题获得一定的感性认识后,你应该加强理论修养,很多时候,这个是必须的;

有必要假设读者在阅读过程中是没有耐心的,本文遵循的写作逻辑注重思维逻辑,如果觉得某个部分啰嗦,你应该跳过这部分,或者直接关闭网页,拒绝浏览。但是文章内容叙述过程,避免不了要用到演绎思维,但我会竭尽全力简化描述,节约你我宝贵时间。
 
二.题目一-相同的球放入相同的盒子(盒子可以为空)
问题描述:将m个相同的球全放入n个相同的盒子,且盒子可以为空,问总共有多少种放法?
PS:使用m,n一般我会有相对固定的习惯或临时决定,变换了脑袋就不太习惯,所以我理解部分人纠结使用m,n这些变量,无所谓啦。
题意理解:这个题目等价于将一个整数m分解为至多n个数的和。相同的球,意味着球是无差异化的,即对于一个盒子而言,区分放法的是放入的个数;相同的盒子意味着对于一种放法而言,5个球2个盒子时,5=2+3与5=3+2是相同的放法。
求解:
我用笔在草稿纸上演算比较小的整数分解,例如5:
5=5
5=3+2=3+1+1
...
我意识到应该对演算形式分类,我想到这种分类方法:
5=5
5=4+1

5=3+2=3+1+1
5=2+2+1=2+1+1+1
5=1+1+1+1+1
就是每次我考虑分解出一个大数,用这个大数如5,4,3,2,1来区分分解的方法,容易证明这种方法是唯一的(证明这个词,你可以忽略它,我没有用严格方法去论证,我想表达的是,这应该是正确的)。对,就是这样。比如5分离出一个大数3,还剩下2,同样也可以继续按这种做法。
然后我为这种分解方法定义一个函数:
               g(m,n,r) 表示:将整数m至多分解为n个数之和,n个数中最大的数为r的所有分法
对于我们的要求解的题目,函数定义为:
               f(m,n)表示:将整数m至多分解为n个数之和所有分法
那么:
               f(m,n) = g(m,n,m)+g(m,n,m-1)+ ... +g(m,n,1)
               g(m,n,r) = g(m-r,n-1,min[r,m-r]) + ... + g(m-r,n-1,1)
得到这个表达式后,熟悉动态规划的朋友应该可以写出程序了,我没有受过ACM培训,对着这样的式子,也曾耷拉着脑袋。这是个递归式,而我们动态规划求解问题的过程用到的是迭代方法。即计算的顺序是:
1=1
2=1+1          |   2
3=1+1+1      |   2+1   |     3
求解3的过程是这样的:
     (1) 最大为1,剩下2。问题缩小为求解2,最大为1的个数。查上表,得知2=1+1,所以这种分法为1种;
     (2) 最大为2,剩下1。问题缩小为求解1,最大数为1(这里会有个min操作)的个数。查表1=1,所以这种分法为1种;
     (3) 最大为3,剩下为0。只有一种。
到这里,应该可以写出程序了。我编码的过程是先写出个简单版本,所以先写了递归版本,然后再写了迭代版本,比较两者的时间差异。具体代码暂时没想好放哪里。
 
三. 题目二-某次无聊,遂google ACM算法题,得一题如下:
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。同时,为了帮助选手能够正确理解题意,主持人还举输出:
结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。
样例:
输入
4 2
1231
输出
62

第一次仅仅觉得暴力搜索可以做,没想到其他的,遂放弃。后来一次等火车的时候,想到一个动态规划的方法, 定义一个函数f(k,n,m)表示的意思为有k个乘号 .n到m的区间的相乘最大。计算f(k,n,m)需要上一步f(k-1,n,m)即可。没有编码,等下次空闲找到一个ACM网站做这道题看能不能够AC。