动态规划：制表"/>
动态规划：制表
动态规划方法之一：制表
为什么要用动态规划：
动态编程是一种算法范例，通过将其分解为子问题来解决给定的复杂问题，并存储子问题的结果，以避免再次计算相同的结果。 以下是一个问题的两个主要属性，表明给定的问题可以使用动态编程来解决。
1。重叠子问题
像分割与征服一样，动态规划将解决方案与子问题相结合。动态编程主要用于需要一次又一次的同一子问题的解决方案。在动态规划中，将子问题的计算解决方案存储在表中，以便不必重新计算。因此，当没有共同（重叠）子问题时，动态编程是无用的，因为如果不再需要解决方案，则没有任何点存储解决方案。例如， 二进制搜索 没有共同的子问题。如果我们采用以下递归程序的斐波纳契数字的例子，则有许多子问题被一再解决。int fib(int n) { if(n <= 1) { return n; } return fib(n-1) + fib(n-2); }
2. 最优子结构
存在以下两种不同的方法来存储值，以便可以重用这些值：a）记忆（自上而下）
b）制表（从上到下）
在这里我只就重叠子问题进行分析，举具体的几个常见的例子，这两天一直在看动态规划的例子，着实叫人头疼，动态规划真是很需要简单的思维，昨天看了一个 一个人写的跳跃游戏二的动态规划（他说这个最简单，可能我太笨了）算法，我调试了好多遍，对它的每一步都快背下来了，却还是一头雾水，今天又看了快一天的动态规划 例子，刚刚对于制表的方法开窍了，赶紧写下来，保存住现在的想法，也和大家分享一下，有错误或者不足希望指出来，一起学习！
Memoization（自上而下）：问题 的记忆式程序类似于递归版本，在计算解决方案之前，它会对查找表进行小修改。我们初始化一个查找数组。每当我们需要解决一个子问题时，我们首先查看查找表。如果预先计算的值在那里，那么我们返回该值，否则我们计算该值并将结果放在查找表中，以便稍后重新使用。
下面我们就从最简单的斐波那契 的动态规划开始！由于本身比较简单所以我就简单说说，主要讨论后面两个例子！
#include<stdio.h>
#define NIL -1
#define MAX 100
intlookup[MAX];//这里是一个备忘录
/* Function to initialize NIL values in lookup table */
void_initialize()
{
inti;
for(i = 0; i < MAX; i++)
lookup[i] = NIL;
}
/* function for nth Fibonacci number */
intfib(intn)
{
if(lookup[n] == NIL)
{
if(n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
returnlookup[n];
}
intmain ()
{
intn = 40;
_initialize();
printf("Fibonacci number is %d ", fib(n));
return0;
}
我想斐波那契学过递归的人都编写过，也都能看懂，大家可以试一下，用上面的方法相比纯递归会很明显缩短了运行时间。
上面的可能还不够扣题，下面我们来点紧扣主题的东西：制表！ b）制表（从上到下）： 给定问题的制表程序以自下而上的方式构建表，并从表返回最后一个条目。例如，对于相同的斐波那契数，我们首先计算fib（0），然后计算fib（1），然后fib（2）然后fib（3）等等。从字面上来说，我们正在建立子问题自下而上的解决方案。
下面是斐波那契的制表方法：
#include<stdio.h>
intfib(intn)
{
intf[n+1];
inti;
f[0] = 0; f[1] = 1;
for(i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
returnf[n];
}
intmain ()
{
intn = 9;
printf("Fibonacci number is %d ", fib(n));
return0;
}
好了，这只是引子帮助大家理解的，我也不多说了， 下面我们来看最长增长序列的问题 让我们讨论最长增长子序列（LIS）问题作为可以使用动态编程解决的示例问题。
最长增长子序列（LIS）问题是找到给定序列的最长子序列的长度，使得子序列的所有元素按增加的顺序排序。 例如，{10,22,9,33,21,50,31,60,80}的LIS长度为6，LIS为{10,22,33,50,60,80}}。
首先我们看到题目，先判断能不能用动态规划的方法。我来说一下我思考的过程： 1.我需要用arr[i]来存储数据，用i对数组的数据进行遍历 2.我需要另一个变量j来遍历i前面的数字，如果arr[j] < arr[i],所以立马你就知道你现在需要一个数组来从最初的i存储LIS 了 首先我们必须提前初始化这个表，当current_lenth长度变化时存入表格 3.我需要一个表，我需要一个数组lis[]来作为表格记录每次到达之前最长增长序列i的长度，后面出现重叠子问题直接调用； | #include<stdio.h> |
我因为一下子看懂了上面这个例子并且自己时间以后又回来看了看之前一直让我头疼的跳跃游戏升级版：
题目描述：
给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标，并且使用最少的跳跃次数。
例如：
A = [2,3,1,1,4], 到达最后一个下标的最少跳跃次数为2.（先跳跃1步，从下标0到1,然后跳跃3步，到达最后一个下标。一共两次）
格式：
第一行输入一个正整数n，接下来的一行，输入数组A[n]。
最后输出最少的跳跃次数。
样例：
输入
5
3 1 1 1 1
输出
2
思想和上面的几乎相同，变动很小，也就初始化的方法和遍历时的意思（算法）便动了 写在前面（我当时困惑的地方，真的是让我头大）：
1.在下面二重循环时，j为什么要小于i？
2.我觉得这个问题没有最优啊，只有一种情况，这个题目有个跳跃游戏一，那个我做出来了而且稍微改一下也可以得到这道题的答案，
但是那道题我就按照自己的思路感觉很简单就出来了，对了我一会试一下在一的基础上能不能改成二动态规划。
3. if(dp[j] + 1 < dp[i])
dp[i] = dp[j] + 1;
// dp[i] = min(&dp[i], &dp[j]+1);
前两局为什么不能用第三句代替呢？
我会在下面代码的注释中解释：
#include<stdio.h>
#include<stdlib.h>
#define MAX 99999
int min(int *a, int *b);
int BestJump(int a[], int len, int *dp);
//动态规划 跳跃二
int main()
{
int n;
int *dp;//申请一个动态数组作为表
printf("请输入元素个数：\n");
scanf("%d", &n);
int a[n];
printf("请输入元素：\n");
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
printf("跳跃了%d次！", BestJump(a,n,dp));
return 0;
}
int BestJump(int a[], int len, int *dp)
{
if(len <= 1)
{
return 0;
}
dp = (int *)malloc((len+1)*sizeof(int));
dp[0] = 0;//下面三行代码是表格的初始化
for(int i = 1; i < len; ++i)
{
dp[i] = MAX;
}
//从数组下标为一的元素开始遍历
for(int i = 1; i < len; ++i)
{
for(int j = 0; j < i; ++j)//这里之所以要小于i是因为我们每一次求得的dp[i]都是i之前需要跳跃的次数，当时我这里一直不明白，其实是因为我没有弄明白这个问题的算法
{
if(a[j] + j >= i)
{
if(dp[j] + 1 < dp[i])
dp[i] = dp[j] + 1;
// dp[i] = min(&dp[i], &dp[j]+1);
break;
}
}
}
return dp[len -1];
}
int min(int *a, int *b)
{
return ((*a)<(*b)?(*a):(*b));
}
至于为啥是最少即最优问题我想这里面可能有贪心的成分吧，就比如a[0] = 3,他可以跳跃到达a[3],a[2],a[1]; 而这里面dp【】每次记录的都是最大的那次，所以最后次数是最少的。我也是今晚感觉对动态规划制表的方法有点感觉了，如果上面有错误的地发，希望指出，我会虚心学习！
#include<stdio.h>
#include<stdlib.h>
#define MAX 99999
int min(int *a, int *b);
int BestJump(int a[], int len, int *dp);
//动态规划 跳跃二
int main()
{
int n;
int *dp;
printf("请输入元素个数：\n");
scanf("%d", &n);
int a[n];
printf("请输入元素：\n");
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
printf("跳跃了%d次！", BestJump(a,n,dp));
return 0;
}
int BestJump(int a[], int len, int *dp)
{
if(len <= 1)
{
return 0;
}
dp = (int *)malloc((len+1)*sizeof(int));
dp[0] = 0;
for(int i = 1; i < len; ++i)
{
dp[i] = MAX;
}
for(int i = 1; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(a[j] + j >= i)
{
if(dp[j] + 1 < dp[i])
dp[i] = dp[j] + 1;
// dp[i] = min(&dp[i], &dp[j]+1);
break;
}
}
}
return dp[len -1];
}
int min(int *a, int *b)
{
return ((*a)<(*b)?(*a):(*b));
}
#include<stdio.h>
#include<stdlib.h>
#define MAX 99999
int min(int *a, int *b);
int BestJump(int a[], int len, int *dp);
//动态规划 跳跃二
int main()
{
int n;
int *dp;
printf("请输入元素个数：\n");
scanf("%d", &n);
int a[n];
printf("请输入元素：\n");
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
printf("跳跃了%d次！", BestJump(a,n,dp));
return 0;
}
int BestJump(int a[], int len, int *dp)
{
if(len <= 1)
{
return 0;
}
dp = (int *)malloc((len+1)*sizeof(int));
dp[0] = 0;
for(int i = 1; i < len; ++i)
{
dp[i] = MAX;
}
for(int i = 1; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(a[j] + j >= i)
{
if(dp[j] + 1 < dp[i])
dp[i] = dp[j] + 1;
// dp[i] = min(&dp[i], &dp[j]+1);
break;
}
}
}
return dp[len -1];
}
int min(int *a, int *b)
{
return ((*a)<(*b)?(*a):(*b));
}
更多推荐
动态规划：制表
发布评论