动态规划-思考解决动态规划问题_你的公司老板给了你一张n×n个格子组成的动态规划

关于动态规划,过了一段时间,自己给自己做一个小结.
给你一道题目:

题目题意：
一个n*n的方格.
从（1，1）进去，从（n,n)出；
每一个交叉点都有花生，每次只能是向下或者向右走。
让你找出走过路线中能踩到的花生的数量最多是多少？

给出的数据分析：
验证正确

思考：

传统思考方式
要思考这个几个东西,但自己总觉得没那么高的水平.(cai)
可行性 阶段，决策，最优子结构，无后效性。

所以我决定找一种更合适我的方式去思考动态规划这类问题:
每个人都有自己喜欢的和习惯,这才是我自己

从集合角度来考虑DP问题
对于合适自己的思考,我通常是将DP问题,化为一个集合的角度去思考,比如下面图片:
这个是自己在做一个问题的思考.

摘花生 表示的属性是max
从（1，1）走到（i，j)的最大值
从（1, 1 ) 走到 (i , j）的所有路线的最大值
f(n,n)就是最大值

动态规划

1.状态表示
f[i][j] 集合 所有从（1，1）走到（i，j)的路线代表的值
属性 ： max /min/数量

2.状态的计算
f[i,j] 整个集合，分而治之
最后一步是从是上面 过来的
最后一步是 从左边过来的 max（左，上） max(f[i-1][j]+w[i][j] f[i][j-1]+w[i][j])

状态的计算 ——集合的划分

划分原则：

1.不重复(有的时候并不需要,而有点时候是需要的)
2.不漏

很重要的划分依据：“最后”：

#include <bits/stdc++.h>
#define pb(a) push_back(a)
#define pf push_front
#define beg begin
#define rb rbegin0
#define re rend
#define nd cout<<endl
#define all(s) s.begin(),s.end()
#define pi acos(-1.0)
#define MaxN  0x3f3f3f3f
#define MinN  0xc0c0c0c0
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=1e3+15;
int n,m;
int dp[N][N];
int w[N][N];
int main()
{
    while(cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));
        for( int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                cin>>w[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+w[i][j];//这个的单独
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41