动态规划之数字三角形暴力递归解法和记忆化搜索与最后的递推

原题链接：数字三角形

解题思路:我们所要解决的问题不过是进行一层层的最大值判断，然后将其相加

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int arr[1010][1010];//把arr看成上面写的g就行了

int n;

int fun(int x1,int y1)

{

if(x1>n) return 0;

else return max(fun(x1+1,y1)+arr[x1][y1],fun(x1+1,y1+1)+arr[x1][y1]); 

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=i;j++)

{

cin>>arr[i][j];

}

}

int fh=fun(1,1);//从第一个开始递

cout<<fh;

}

接下来是记忆化搜索的代码

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int arr[1010][1010];

int brr[1010][1010];/*记忆数组 ，

                      8

                1          0

                      4

当1和0都递到4时，1已经记录过4后面的了，直接返回判断4的结果*/

int n; 

int  sum;//用sum来记录结果

int fun(int x1,int y1)

{

if(brr[x1][y1])   return brr[x1][y1];//如果出现第2个一样的，返回第一个的值；

if(x1>n) return 0;

else         sum=max(fun(x1+1,y1)+arr[x1][y1],fun(x1+1,y1+1)+arr[x1][y1]);

brr[x1][y1]=sum;

return sum;

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=i;j++)

{

cin>>arr[i][j];

}

}

int fh=fun(1,1);

cout<<fh;

}

接下来是递推

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int arr[1010][1010];

int brr[1010][1010];

int f[1010][1010];

int n；

int main()

{

        cin>>n;

        for(int i=1;i<=n;i++)

        {

                for(int j=1;j<=i;j++)

               {

                        cin>>arr[i][j];

                }

        }

        for(int i=n;i>=1;i--)

        {

            for(int j=1;j<=n;j++)

            {

                    f[i][j]=max(f[i+1][j]+arr[i][j],f[i+1][j+1]+arr[i][j]);//左下角往右上角推

             }

        }

cout<<f[1][1];

        cout<<fh;

}