金币馅饼（动态规划走格子）

秒速五厘米 2023-01-13 01:46 162阅读 0赞

https://ac.nowcoder.com/acm/problem/25147  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

能走的方式，如图：  
红色的位置置零  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 1]

当 j = 2， i 能选的位置 ，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 2]  
当 j = 3， i能选的位置，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 3]  
以此类推：

ac代码：

#include<bits/stdc++.h>
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    using namespace std;
    
    const int N = 110;
    const int M = 110;
    
    int a[N][N];
    int f[N][N];
    
     int maxPathSum(int n, int m) 
     { 
        f[1][1] = a[1][1];  // position of beginning
    	for (int i = 2; i <= n; i ++)  f[i][1] = 0;  // set 0
    	for (int j = 2; j <= m; j ++){ 
    		for (int i = 1; i <= j; i ++){ 
    			f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i][j]);
    			f[i][j] = max(f[i][j], f[i + 1][j - 1] + a[i][j]);
    			f[i][j] = max(f[i][j], f[i][j - 1] + a[i][j]);
    		// cout << i << " " << j << " " << f[i][j] << endl;
    		}
    	}
          return f[n][m];
     }
    
    void sovle()
    { 
        int n, m;
        cin >> n >> m;
        
        rep(i,1,n)
            rep(j,1,m)
                cin >> a[i][j];
            
        int ans = maxPathSum(n, m);
        cout << ans;
    }
    
    int main()
    { 
        ios;
        sovle();
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221022/20e3c4cc5ec3411a94d806936a7758b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 1]: /images/20221022/872dd2b4dd9645288a58058a62de7dae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 2]: /images/20221022/f5b126243bcd4fc4b42ed502157afac7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70 3]: /images/20221022/94b3e7c60a814a798a26438940fe8634.png