动态规划
最长子序列问题
最长上升子序列及最长下降子序列
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入格式：
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出格式：
输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
输入样例：
8
300 207 155 300 299 170 158 65
输出样例：
6
最长公共子序列（LCS)
例如：有字符串s1，s2，按下列方式填表得到公式：
可求出LCS长度。
之后利用回溯法，斜上方的方格中，s1元素等于s2，则跳到斜上方方格，否则向左或者向上走。可求出序列（不一定唯一，只能求出其中一个）
例：两种水果杂交出一种新水果，现在给新水果取名，要求这个名字中包含以前两种水果的字母，且名字尽量短，即：以前的水果名字arr1、arr2是新水果名arr的子序列，使用动态规划的思想设计算法得到新水果名arr。
输入格式:
以空格分开两个水果的名字
输出格式：
新水果的名字
输入样例：
apple peach
输出样例：
appleach
代码如下：
#include<stdio.h>
#include<string.h>
/**
求最大值
**/
int max(int a, int b) {
if (a > b) {
return a;
}
else {
return b;
}
}
/**
动态规划求最长公共子序列
**/
void Lcs(char a[], char b[], int dp[][10]) {
int a_length, b_length;
a_length = strlen(a);
b_length = strlen(b);//求出两个字符串的长度
memset(dp, 0, sizeof(dp));
for (int m = 1; m <= a_length; m++) {//填写m+1行n+1列数组
for (int n = 1; n <= b_length; n++) {
if (a[m - 1] == b[n - 1]) {
dp[m][n] = dp[m - 1][n - 1] + 1;
}
else {
dp[m][n] = max(dp[m - 1][n], dp[m][n - 1]);
}
}
}
}
/**
构建新水果名
**/
int FindLcs(char a[], char b[], int dp[][10],char c[]) {
int i, j ,z= 0;
i = strlen(a); j = strlen(b);
while (i != 0 && j != 0) {
if (a[i - 2] == b[j - 2]) {
c[z] = a[i-1];
i--; j--; z++;
}
else if (dp[i - 1][j] < dp[i][j - 1]) {
c[z] = b[j-1];
j--; z++;
}
else if (dp[i][j - 1] <= dp[i - 1][j]) {
c[z] = a[i-1];
i--; z++;
}
}
return z;
}
int main() {
char a[10]; char b[10]; char c[20];
int i = 0; int a_length = strlen(a);
int b_length = 0;
int dp[10][10];
scanf("%s", &a);
scanf("%s", &b);
Lcs(a, b, dp);
int c_length = FindLcs(a, b, dp,c);
for (int z = c_length -1; z >= 0; z--) {
printf("%c", c[z]);
}
return 0;
}
机器人问题
简单路径规划
规定方向寻找路线条数
如图，从吃冰激凌的皮卡丘走到吃苹果的皮卡丘需要两步：
1、吃冰激凌的皮卡丘------>吃棒棒糖的皮卡丘/喝咖啡的皮卡丘
2、吃棒棒糖的皮卡丘/喝咖啡的皮卡丘------->吃苹果的皮卡丘
公式如下：
按照此规律递归填数就ok。
例：一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求机器人从（0,0）到（m，n）有多少条路径。（目前有个问题，为什么走到（4，5）是35，我觉得是（3，4）是35）
输入格式:
以空格分开m，n
输出格式：
路径条数
输入样例：
4 5
输出样例：
35
int lujing(int m,int n) {
int i,j;
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
return a[m-1][n-1];
}
进阶路径规划
除了规定方向还要设置雷区
可考虑把所有路径列出来再删去以禁区为起点到终点的路径（还未实现）