高精度乘法
#include <bits/stdc++.h>
using namespace std;
int a[100],b[100],c[100];
int main() {
string s1,s2,t;
cin>>s1>>s2;
for(int i=0;i<s1.length();i++)
{
a[i]=s1[s1.length()-i-1]-'0';
}
for(int i=0;i<s2.length();i++)
{
b[i]=s2[s2.length()-i-1]-'0';
}
for(int i=0;i<s1.length();i++)
{
int carry=0;
for(int j=0;j<s2.length();j++)
{
c[i+j]+=a[i]*b[j]+carry;
carry=c[i+j]/10;
c[i+j]%=10;
}
// 每一遍循环之后的进位
c[i+s2.length()]+=carry;
}
int index=s1.length()+s2.length();
//删除前导零
while(c[index]==0&&index>0)
index--;
for(int i=index;i>=0; i--)
cout<<c[i];
cout<<endl;
return 0;
}
/* input: 6666660000 8888000 output: 59253274080000000 */
赚金币（动态规划）
问题描述：有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入：
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出：最多能拿金币数量。
样例1：
输入：
3 3
1 3 3
2 2 2
3 1 2
输出：
11
样例2：
输入：
4 4
1 2 3 4
0 6 5 7
9 0 4 0
5 3 2 1
输出：
22
动态规划：
动态规划的一般步骤：
第一步：定义数组元素含义：通常定义一个数组dp来保存历史数据
第二步：找出数组元素之间的关系（动态规划的核心）
第三步：找出数组的初始元素值：通过元素之间的关系，从后往前进行归纳，一直到最开始的那个基本元素，确定整个数组的值。
通过初始值和关系式得到整个dp数组的值。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n,i,j;
cin>>m>>n;
int num[m][n],dp[m][n];
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>num[i][j];
dp[i][j]=0;
}
}
//初始化
dp[0][0]=num[0][0];
for(i=1;i<m;i++)
{
dp[i][0]=dp[i-1][0]+num[i][0];
dp[0][i]=dp[0][i-1]+num[0][i];
}
//确定关系：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+num[i][j];
for(i=1;i<m;i++)
{
for(j=1;j<n;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+num[i][j];
}
}
cout<<dp[m-1][n-1]<<endl;
return 0;
}
华为机试题-迷宫问题（回溯）
描述：
定义一个二维数组 N*M ，如5×5数组下所示：
int maze[5][5]= {
0,1,0,0,0,
0,1,1,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围：2≤n,m≤10
输入：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解，不考虑有多解的情况，即迷宫只有一条通道。
输出描述：左上角到右下角的最短路径，格式如样例所示。
样例1：
输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
示例2
输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
输出：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define N 10
int sign[N][N],pos[1000][2],n,m,cnt,maze[N][N],flag;
void dfs(int x,int y)
{
pos[cnt][0]=x;pos[cnt][1]=y;cnt++;
//pos二维数组记录到达位置的下标
sign[x][y]=1;
//sign二维数组在相同位置值1，表示这个位置已经走过
if(x==n-1&&y==m-1)
{
flag=1;
return;
//到达终点，flag置1，并返回上一级dfs递归调用
}
int i,j,k;
int x_incre[4]={
0,1,0,-1},y_incre[4]={
1,0,-1,0};
for(k=0;k<4;k++)
{
i=x+x_incre[k];j=y+y_incre[k];
//i,j为下次试探的位置
if(i>=0&&j>=0&&i<n&&j<m&&!maze[i][j]&&!sign[i][j])
{
//不能超出迷宫，也不能走障碍和已经走过的点
dfs(i,j);
//进入下一步位置的试探
if(flag)
return;
//试探的路径可以达到终点，返回上一级dfs调用
}
}
sign[i][j]=0;
cnt--;
//如果没有试探出终点而返回，也没能在4次方向试探中找到可走的路那么说明这个点走错了，标记这个点没走过，并将坐标弹出，结束这层dfs，返回上一层
}
int main()
{
int i,j,startx=0,starty=0;
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>maze[i][j];
dfs(startx,starty);
//起始位置为（0，0）
for(i=0;i<cnt;i++)
cout<<"("<<pos[i][0]<<","<<pos[i][1]<<")"<<endl;
return 0;
}
参考：
https://blog.csdn.net/Cooler_z/article/details/122461999
文章评论