动态规划数组声明

最近复习动态规划的时候发现一个问题，有的时候动态规划数组声明是m+1,有的时候是m, 什么时候声明m, 什么时候声明m+1呢？ 谢谢大家
举个例子
Coin change 2  这个就是声明m+1
[color=rgba(0, 0, 0, 0.65)]You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
[color=rgba(0, 0, 0, 0.65)]

[color=rgba(0, 0, 0, 0.650980392156863)]public class Solution {
[color=rgba(0, 0, 0, 0.650980392156863)]    /**
[color=rgba(0, 0, 0, 0.650980392156863)]    * @param amount: a total amount of money amount
[color=rgba(0, 0, 0, 0.650980392156863)]     * @param coins: the denomination of each coin
[color=rgba(0, 0, 0, 0.650980392156863)]     * @return: the number of combinations that make up the amount
[color=rgba(0, 0, 0, 0.650980392156863)]     */
[color=rgba(0, 0, 0, 0.650980392156863)]    public int change(int amount, int[] coins) {
[color=rgba(0, 0, 0, 0.650980392156863)]        // write your code here
[color=rgba(0, 0, 0, 0.650980392156863)]        int[] dp = new int[amount + 1];
[color=rgba(0, 0, 0, 0.650980392156863)]        dp[0] = 1;
[color=rgba(0, 0, 0, 0.650980392156863)]        for (int i = 0; i < coins.length; i++) {
[color=rgba(0, 0, 0, 0.650980392156863)]            for (int j = coins[i]; j <= amount; j++) {
[color=rgba(0, 0, 0, 0.650980392156863)]                dp[j] += dp[j - coins[i]];
[color=rgba(0, 0, 0, 0.650980392156863)]            }
[color=rgba(0, 0, 0, 0.650980392156863)]        }
[color=rgba(0, 0, 0, 0.650980392156863)]        return dp[amount];
[color=rgba(0, 0, 0, 0.650980392156863)]    }
[color=rgba(0, 0, 0, 0.650980392156863)]}

[color=rgba(0, 0, 0, 0.650980392156863)]

Unique Paths 这个就是声明m


class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i<n; i++){
            dp[0][i] = 1;
        }

        for(int i =0; i<m; i++){
            dp[i][0] = 1;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

一般而言主要是考虑“什么都不选”的empty的情况下会选择m+1，但m+1的很多情况都是可以用size = m 同时判断是否越界来做。m-1的情况我好像遇到的很少。

被大神翻牌子~~~， 开心，可以没懂，可以具体讲讲吗？谢谢

如果定义的时候是  前i个 那就是m+1 因为前0个默认是default情况

如果定义的是index i的情况下xxxx 那就是m.
这个看个人习惯. 而且你两者多试试就知道了. 有些时候如果需要用m+1 而你用m  就会要多余额外的判断corner cases

对应这个题，如果我定义dp[i][j]是我只用前面i个coins来拼出amount = j的最小coins数目
如果用m，那么就需要考虑我什么都不用还能拼出amount = j的情况。那么就需要考虑i-1的时候，也就是i=0时 i-1越界。
如果用m+1，那么我i其实是从i=1开始的 就不需要考虑i-1 = -1的情况了。
本质上没什么差别

很早前做的总结，不知道现在还有效不

string （match）相关的是(M+1)*(N+1)，其他都是M*N

M*N中讨论是有多少种方法可以的，绝大多可以O(N) space解决。