暴力递归到动态规划

程序1:汉诺塔问题

#include<iostream> // N层汉诺塔问题
using namespace std;
#include<string>

void process(int N, string from,string to,string help)
{
    if(N == 1)
    {
        cout<<"Move 1 from  "+ from +"to "+ to<<endl;
    }
    else
    {
        process(N-1,from, help, to);
        cout<<"Move " +  to_string(N) + " from "+ from +"to "+ to<<endl;
        process(N-1, help, to, from);
    }

}

int main() 
{
    process(3,"左"," 右", "中");
    return 0;
}

程序2:打印字符串的全部子序列

#include<iostream> // 打印字符串的全部子序列
using namespace std;
#include<string>

void printAllSub(string str,int i,string res)
{
    if(i == str.length())
    {
        cout<<res<<endl;
        return;
    }
    printAllSub(str, i+1, res);
    printAllSub(str, i+1,res+=str[i]);
}

int main() 
{
    string test = "abc";
    printAllSub(test,0,"");
    return 0;
}

程序3:二维数组沿途经过的和最小,+数组中求几个数的值,暴力版本

#include<iostream> // 二维数组沿途经过的和最小,+数组中求几个数的值,暴力版本
using namespace std;
#include<string>


int walk(int* arr[], int i, int j,int row,int clo)
{
    if(i == row - 1 && j == clo - 1)
    {
        return arr[i][j];
    }
    if(i == row-1)
    {
        return arr[i][j] + walk(arr,i,j+1, row,clo);
    }
    if(j == clo - 1)
    { 
        return arr[i][j] + walk(arr, i+1,j, row,clo);
    }  
    int right = walk(arr, i,j+1, row,clo);  //当前位置,右边位置到右下角的最短路径和
    int down = walk(arr, i+1,j, row,clo);  //当前位置,下边位置到右下角的最短路径和
    return arr[i][j] + min(right,down);
}

bool isSum(int *arr, int i, int sum, int aim)   //数组中几个数的和是否等于给定值
{
    if(i == sizeof(arr) / sizeof(int))
    {
        return sum == aim;
    }
    return isSum(arr, i+1, arr[i]+sum, aim) || isSum(arr, i+1,sum,aim);
}

int main() 
{
    int arr[2][2] = {1,2,3,4};
    int arr2[3] = {1,4,8};
    cout<<isSum(arr2,0,0,5)<<endl;
    return 0;
}

程序4:几个经典的动态规划,二维数组做参数传递问题未解决

#include<iostream> // 几个经典的动态规划,二维数组做参数传递问题未解决
using namespace std;
#include<string>


int process1(int arr[], int index,int aim,int len)
{
    int res = 0;
    if(index == len)
    {
        return res = aim==0?1:0;
    }
    else
    {
        for(int i=0;arr[index] * i<=aim;i++)
        {
            res+=process1(arr,index+1,aim - arr[index] * i,len);
        }
    }
}
int const1(int *arr, int aim,int len)  //凑钱数,暴力递归方法
{
    if(arr == nullptr | aim<0 | len==0)
    {
        return 0;
    }
    return process1(arr,0,aim, len);
}
int process2(int arr[], int index,int aim,int len,int* mapm)    //二维数组做参数传递问题未解决
{
    int res = 0;
    if(index == len)
    {
        return res = aim ==0?1:0;
    }
    else
    {
        int mapValue = 0;
        for(int i=0;arr[index]*i<=aim;i++)
        {
            // mapValue = mapm[index+1][aim-arr[index]*i];
            mapValue = *(mapm+(index+1)*(aim+1) + (aim-arr[index]*i));
            if(mapValue!=0)
            {
                res+=mapValue==-1?0:mapValue;
            }
            else
            {
                res+=process2(arr,index+1,aim-arr[index]*i,len,mapm);
            }

        }
    }
    *(mapm+index*(aim+1) + aim) = res==0?-1:res;
    return res;
}
int const2(int *arr, int aim,int len) // 凑钱数,记忆力搜索方法
{
    if(arr == nullptr |aim <0 | len ==0)
    {
        return 0;
    }
    int mapm[len+1][aim+1];
    return process2(arr,0,aim, len,(int*)mapm);
}

int s1(int n)   //台阶问题
{
    if(n<0)
    {
        return 0;
    }
    if(n == 1 ||n ==2)
    {
        return n;
    }
    return s1(n-1) + s1(n-2);
}


void show(int *arr, int m,int n)
{
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            *(arr+n*i+j)=i*j;
        }
    }
}
int main() 
{

    int a[5][5];
    show((int *)a, 5,5);
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<*(a+i*5+j)<<"    ";
        }
        cout<<endl;
    }
    return 0;
}